A Different Short Proof of Brooks’ Theorem
Landon Rabern
Discussiones Mathematicae Graph Theory, Tome 34 (2014), p. 633-634 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

Lovász gave a short proof of Brooks’ theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case.

Publié le : 2014-01-01
EUDML-ID : urn:eudml:doc:267828 
@article{bwmeta1.element.doi-10_7151_dmgt_1721,
     author = {Landon Rabern},
     title = {A Different Short Proof of Brooks' Theorem},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {34},
     year = {2014},
     pages = {633-634},
     zbl = {1295.05110},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1721}
}

Landon Rabern. A Different Short Proof of Brooks’ Theorem. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 633-634. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1721/

[1] R.L. Brooks, On colouring the nodes of a network, in: Math. Proc. Cambridge Philos. Soc. 37 Cambridge Univ. Press (1941) 194-197. | Zbl 0027.26403

[2] R. Diestel, Graph Theory (Fourth Ed., Springer Verlag, 2010).

[3] A.D. King, Hitting all maximum cliques with a stable set using lopsided independent transversals, J. Graph Theory 67 (2011) 300-305. doi:10.1002/jgt.20532[WoS][Crossref] | Zbl 1231.05205

[4] A.V. Kostochka, Degree, density, and chromatic number, Metody Diskret. Anal. 35 (1980) 45-70 (in Russian).

[5] L. Lov´asz, Three short proofs in graph theory, J. Combin. Theory (B) 19 (1975) 269-271. doi:10.1016/0095-8956(75)90089-1[Crossref]

[6] L. Rabern, On hitting all maximum cliques with an independent set, J. Graph Theory 66 (2011) 32-37. doi:10.1002/jgt.20487[Crossref][WoS] | Zbl 1222.05201

[7] H. Tverberg, On Brooks’ theorem and some related results, Math. Scand. 52 (1983) 37-40. | Zbl 0512.05028