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, χCAP(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 χCAP(G)≤χ(G)−1. Greene has conjectured that there is an unbounded function f such that χCAP(G)≥f(χ(G)). In this article we prove Greene's conjecture.