Abstract:
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)$.