RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2009 Volume 21, Issue 4, Pages 105–128 (Mi dm1076)

This article is cited in 2 papers

Nondegenerate colourings in the Brooks theorem

N. V. Gravin


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

UDC: 519.2

Received: 22.12.2007
Revised: 10.06.2008

DOI: 10.4213/dm1076


 English version:
Discrete Mathematics and Applications, 2009, 19:5, 533–553

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025