|
This article is cited in 2 scientific papers (total 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)$.
Received: 22.12.2007 Revised: 10.06.2008
Citation:
N. V. Gravin, “Nondegenerate colourings in the Brooks theorem”, Diskr. Mat., 21:4 (2009), 105–128; Discrete Math. Appl., 19:5 (2009), 533–553
Linking options:
https://www.mathnet.ru/eng/dm1076https://doi.org/10.4213/dm1076 https://www.mathnet.ru/eng/dm/v21/i4/p105
|
Statistics & downloads: |
Abstract page: | 517 | Full-text PDF : | 216 | References: | 66 | First page: | 20 |
|