Josef BUCKO & Peter MIHÓK

(Technical University of Košice, Slovakia)

Generalized colourings

Peter MIHÓK: Generalized Colourings I - Fractional Invariants
(joint work with R. Soták and J. Oravcová)

A graph property $\mcp$ is any nonempty isomorphism-closed class of simple (finite or infinite) graphs. We will consider additive and hereditary graph properties i.e. classes closed under disjoint union and subgraphs.

Let $\omega(G); \chi_f(G); \chi_c(G); \chi(G); ch(G); col(G); \Delta(G)$ be the clique number; fractional chromatic number; circular chromatic number; chromatic number, choice number, colouring number and maximum degree of a graph $G$, respectively .It is well known, that for any graph $G$ we have

$$\omega(G) \le \chi_f(G) \le \chi_c(G) \le \chi(G) \le ch(G) \le col(G) \le \Delta(G)+1.$$

In our talk we will introduce the generalized versions of above mentioned chain of invariants and present some basic results on this topic.

Josef BUCKO: Generalized Colourings II - Weakly Universal Graphs
(joint work with P. Mihók)

We consider countable graphs. A graph property $\mcp$ is of finite character if a graph $G$ has a property $\mcp$ if and only if every finite induced subgraph of $G$ has a property $\mcp$. Let $\mcp_1,\mcp_2,\dots,\mcp_n$ be graph properties of finite character, a graph $G$ is said to be (uniquely) ()-partitionable if there is an (exactly one) partition of $V(G)$ such that $G[V_i]\in \mcp_i$ for $i=1, 2, \dots ,n$. Let us denote by $\mcr = \mcircPn$ the class of all $(\mcp_1,\mcp_2,\dots,\mcp_n)$-partitionable graphs. A property $\mcr = \mcircPn, n\ge 2$ is said to be reducible. We will show that any reducible additive graph property $\mcr$ of finite character has a uniquely ()-partitionable countable generating graph. Moreover, we prove that $\mcircPn$ has a weakly universal graph if and only if each property $\mcp_i$ has a weakly universal graph.