Independent sets in k-chromatic graphs (Q1076033)

A k-colouring of a graph G is a map \(\Psi\) : V(T)\(\to \{1,2,...,k\}\) such that no two adjacent vertices have the same image. A k-critical graph is a connected k-chromatic graph in which each of its edges is critical, i.e., the chromatic number of G-e is k-1 for any edge e of G. A graph G is said to have property \(P_ k\) if in each k-colouring of G using all k colours there are k independent vertices receiving all the colours. The main results of this paper are: (1) For each \(k\geq 3\), there is a k- critical graph having property \(P_ k\) (which proves an unpublished conjecture of P. Erdős); (2) Each k-chromatic (k\(\geq 3)\) graph of girth at least 6 has property \(P_ k\) or is a cycle of length 7. Among many other results, the author also constructs some k-chromatic graphs having property \(P_{k+1}\) and gives a characterization of k-chromatic (k\(\geq 3)\) graphs G with girth greater than \(5(k+5)\) such that G has property \(P_{k+1}\). Several open problems are also mentioned in this paper.