Brooks' theorem via the Alon-Tarsi theorem

DOI10.1016/J.DISC.2010.07.019zbMATH Open1222.05061OpenAlexW1988233594WikidataQ57601408 ScholiaQ57601408MaRDI QIDQ712277FDOQ712277

Authors Jan Hladký, Uwe Schauz, Daniel Král'

Publication date 28 October 2010

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringBrooks' theoremAlon-Tarsi method

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We give a proof of Brooks' theorem and its list coloring extension using the algebraic method of Alon and Tarsi; this also shows that the Brooks' theorem remains valid in a more general game coloring setting.

Recommendations

• Brooks' Theorem and Beyond
• The colour theorems of Brooks and Gallai extended
• A unified proof of Brooks' theorem and Catlin's theorem
• Brooks-type theorems for choosability with separation
• A different short proof of Brooks' theorem

Cites work

• scientific article; zbMATH DE number 3920511 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
• Circular choosability of graphs
• Circular choosability via combinatorial Nullstellensatz
• Circular chromatic number: A survey
• Circular degree choosability
• Colorings and orientations of graphs
• Combinatorial Nullstellensatz
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• Mr. Paint and Mrs. Correct
• On a four-colour theorem.
• On two questions about circular choosability
• Recent developments in circular colouring of graphs
• Star chromatic number
• The colour theorems of Brooks and Gallai extended
• Three short proofs in graph theory

Cited in

(24)

• Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
• On the Alon-Tarsi number of semi-strong product of graphs
• Graph polynomials and paintability of plane graphs
• The Alon-Tarsi number of two kinds of planar graphs
• Brooks' theorem on powers of graphs
• On a Lovász-type lemma, applied to Brooks' theorem for list-colouring
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• Dynamic coloring parameters for graphs with given genus
• Application of polynomial method to on-line list colouring of graphs
• Improved lower bounds on the number of edges in list critical and online list critical graphs
• Partial online list coloring of graphs
• Orientations of graphs with prescribed weighted out-degrees
• The list-chromatic index of \(K_6\)
• An NC algorithm for Brooks' theorem
• Critically paintable, choosable or colorable graphs
• A different short proof of Brooks' theorem
• On two generalizations of the Alon-Tarsi polynomial method
• Beyond degree choosability
• Dirac's theorem on chordal graphs implies Brooks' theorem
• The tournament scheduling problem with absences
• Brooks' Theorem and Beyond
• Proof of the list edge coloring conjecture for complete graphs of prime degree
• Strengthening \((a,b)\)-choosability results to \((a,b)\)-paintability
• List-coloring claw-free graphs with \(\Delta-1\) colors

This page was built for publication: Brooks' theorem via the Alon-Tarsi theorem

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