Peter MIHÓK

(Mathematical Institute, Slovak Academy of Science, Koszyce)

A Short Survey on Generalized Colouring and the Existence of Uniquely Colourable Graphs

Let ${\cal P}$ be a graph property. A vertex $({\cal P},n)$-coloring of a graph $G$ is a partition $\{ V_{1}, V_{2}, \ldots , V_{n}\}$ of its vertex set $V(G)$ into n classes such that each $V_i$ induces a subgraph $G[V_i]$ with property ${\cal P}$. A graph $G$ is said to be uniquely $({\cal P},n)$-colorable, $n\geq 2$, if $G$ has exactly one $({\cal P},n)$-partition. We will present a shory survey on the existence of uniquely colorable graphs with respect to additive induced-hereditary properties. Given an additive induced-hereditary property ${\cal P}$, we will show that uniquely $({\cal P},n)$-partitionable graphs exist if and only if the property ${\cal P}$ is irreducible. In particular, this implies that for every induced-hereditary property with finitely many connected minimal forbidden induced subgraphs there are uniquely partitionable graphs. Moreover, each $({\cal P},n)$-colorable graph $G$ is an induced subgraph of a uniquely $({\cal P},n)$-colorable graph.

Research supported in part by Slovak VEGA Grant 2/7141/07

Serdecznie zapraszamy wszystkich chêtnych !