A Different Short Proof of Brooks’ Theorem

• Autorzy: Landon Rabern
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

coloring; clique number; maximum degree

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 3
• Strony: 633-634

Daty

wydano

2014-08-01

otrzymano

2012-05-28

zaakceptowano

2013-01-03

online

2014-07-16

Twórcy

autor

Landon Rabern

• Arizona State University School of Mathematical & Statistical Sciences

Bibliografia

• [1] R.L. Brooks, On colouring the nodes of a network, in: Math. Proc. Cambridge Philos. Soc. 37 Cambridge Univ. Press (1941) 194-197.
• [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]
• [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]
• [7] H. Tverberg, On Brooks’ theorem and some related results, Math. Scand. 52 (1983) 37-40.

Identyfikatory

DOI

10.7151/dmgt.1721