A different short proof of Brooks' theorem

DOI10.7151/DMGT.1721MaRDI QIDQ2509552zbMATH OpenOpenAlexFDO

Authors Landon Rabern

Publication date 28 July 2014

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://arxiv.org/abs/1205.3253

zbMATH Keywords

clique numbercoloringmaximum degree

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Abstract: Lov'asz 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. Then we show how to extend the result to (online) list coloring via the Kernel Lemma.

Recommendations

• Brooks' Theorem and Beyond
• Short proofs of classical theorems
• A short proof of Brooks’ Theorem for vertex arboricity
• On a Lovász-type lemma, applied to Brooks' theorem for list-colouring
• Brooks' theorem via the Alon-Tarsi theorem

Cites work

• Graph theory
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• scientific article; zbMATH DE number 3719178 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• On Brooks' theorem and some related results.
• On hitting all maximum cliques with an independent set
• Three short proofs in graph theory

Cited in

(11)

• A characterisation of some 2-connected graphs and a comment on an algorithmic proof of Brooks' theorem
• On a Lovász-type lemma, applied to Brooks' theorem for list-colouring
• Brooks' Theorem and Beyond
• Short proofs of classical theorems
• A unified proof of Brooks' theorem and Catlin's theorem
• Four proofs of the directed Brooks' theorem
• Yet another proof of Brooks' theorem
• Special issue in honour of Landon Rabern
• Dirac's theorem on chordal graphs implies Brooks' theorem
• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• Brooks' theorem via the Alon-Tarsi theorem

This page was built for publication: A different short proof of Brooks' theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2509552)