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

作者：Zhou Bing^*

来源：Discrete Mathematics, 2013, 313(20): 2146-2149.

DOI：10.1016/j.disc.2013.05.012

• Chromatic capacity
• Chromatic number
• Vertex colouring
• Edge colouring

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, chi(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 chi(CAP) (G) %26lt;= chi (G) - 1. Greene has conjectured that there is an unbounded function f such that chi(CAP) (G) %26gt;= f (chi (G)). In this article we prove Greene%26apos;s conjecture.

• 出版日期2013-10-28