Nondegenerate colourings in the Brooks theorem

N. V. Gravin

Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 105-128

Résumé

Let $c\ge2$ and $p\ge c$ be two integers. We say that a proper colouring of the graph $G$ is $(c,p)$-nondegenerate, if for any vertex of $G$ of degree at least $p$ there are at least $c$ vertices of different colours adjacent to it. In this research we prove the following result which generalises the Brooks theorem. Let $D\ge3$ and $G$ be a graph without cliques on $D+1$ vertices and a degree of any vertex in this graph be no greater than $D$. Then for any integer $c\ge2$ there is a proper $(c,p)$-nondegenerate vertex $D$-colouring of $G$, where $p= (c^3+8c^2+19c+6)(c-1)$.