A lower bound for the chromatic capacity in terms of the chromatic number of a graph

When the vertices and edges are coloured with k colours, an edge is called monochromatic if the edge and the two vertices incident with it all have the same colour. The chromatic capacity of a graph G , χ C A P ( G ) , is the largest integer k such that the edges of G can be coloured with k colours in such a way that when the vertices of G are coloured with the same set of colours, there is always a monochromatic edge. It is easy to see that χ C A P ( G ) ≤ χ ( G ) − 1 . Greene has conjectured that there is an unbounded function f such that χ C A P ( G ) ≥ f ( χ ( G ) ) . In this article we prove Greene’s conjecture.