Geodesic
Nondegenerate colourings in the Brooks theorem
Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 105-128.

Voir la notice de l'article provenant de la source Math-Net.Ru

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)$. 
@article{DM_2009_21_4_a9,
     author = {N. V. Gravin},
     title = {Nondegenerate colourings in the {Brooks} theorem},
     journal = {Diskretnaya Matematika},
     pages = {105--128},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2009_21_4_a9/}
}
TY  - JOUR
AU  - N. V. Gravin
TI  - Nondegenerate colourings in the Brooks theorem
JO  - Diskretnaya Matematika
PY  - 2009
SP  - 105
EP  - 128
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2009_21_4_a9/
LA  - ru
ID  - DM_2009_21_4_a9
ER  - 
%0 Journal Article
%A N. V. Gravin
%T Nondegenerate colourings in the Brooks theorem
%J Diskretnaya Matematika
%D 2009
%P 105-128
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2009_21_4_a9/
%G ru
%F DM_2009_21_4_a9
N. V. Gravin. Nondegenerate colourings in the Brooks theorem. Diskretnaya Matematika, Tome 21 (2009) no. 4, pp. 105-128. http://geodesic.mathdoc.fr/item/DM_2009_21_4_a9/

[1] Bondy J. A., Murty U. S. R., Graph theory with applications, Elsevier, New York, 1976 | MR

[2] Hong-Jian L., Montgomery B., Poon Hoifung, “Upper bounds of dynamic chromatic number”, Ars Combinatoria, 68 (2003), 193–201 | MR | Zbl

[3] Montgomery B., Dynamic colouring, Ph. D. Dissertation, West Virginia Univ., 2001

[4] Brooks R. L., “On colouring the nodes of network”, Proc. Cambridge Philos. Soc., 37 (1941), 194–197 | DOI | MR | Zbl

[5] Meng X., Miao L., Li Z. R., Su B., “The conditional colouring numbers of pseudo-Halin graphs”, Ars Combinatoria, 79 (2006), 3–9 | MR | Zbl

[6] Fan Suohai, Lai Hong-Jian, Lin Jianliang, Montgomery B., Tao Zhishui, “Conditional colourings of graphs”, Discrete Math., 16 (2006), 1997–2004 | MR | Zbl

[7] Hind H., Molloy M., Reed B., “Colouring a graph frugally”, Combinatorica, 17 (1997), 469–482 | DOI | MR | Zbl

[8] Godsil C., Royle G., Algebraic graph theory, Springer, Berlin, 2001 | MR

[9] Lovász L., “On decomposition of graphs”, Stud. Sci. Math. Hungar., 1 (1966), 237–238 | MR | Zbl