Brooks' theorem via the Alon-Tarsi theorem
From MaRDI portal
Publication:712277
DOI10.1016/J.DISC.2010.07.019zbMATH Open1222.05061arXiv0905.3475OpenAlexW1988233594WikidataQ57601408 ScholiaQ57601408MaRDI QIDQ712277FDOQ712277
Authors: Jan Hladký, Uwe Schauz, Daniel Král' 
Publication date: 28 October 2010
Published in: Discrete Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0905.3475
Recommendations
Cites Work
- Mr. Paint and Mrs. Correct
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Three short proofs in graph theory
- Combinatorial Nullstellensatz
- Recent developments in circular colouring of graphs
- Star chromatic number
- Circular chromatic number: A survey
- Colorings and orientations of graphs
- Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
- Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
- On two questions about circular choosability
- Circular choosability of graphs
- The colour theorems of Brooks and Gallai extended
- Title not available (Why is that?)
- Circular degree choosability
- Circular choosability via combinatorial Nullstellensatz
- On a four-colour theorem.
Cited In (24)
- A different short proof of Brooks' theorem
- Dirac's theorem on chordal graphs implies Brooks' theorem
- Graph polynomials and paintability of plane graphs
- List-coloring claw-free graphs with \(\Delta-1\) colors
- Application of polynomial method to on-line list colouring of graphs
- Beyond degree choosability
- The Alon-Tarsi number of two kinds of planar graphs
- Brooks' theorem on powers of graphs
- Critically paintable, choosable or colorable graphs
- An NC algorithm for Brooks' theorem
- On two generalizations of the Alon-Tarsi polynomial method
- On a Lovász-type lemma, applied to Brooks' theorem for list-colouring
- On the Alon-Tarsi number of semi-strong product of graphs
- Dynamic coloring parameters for graphs with given genus
- The tournament scheduling problem with absences
- Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
- Proof of the list edge coloring conjecture for complete graphs of prime degree
- Partial online list coloring of graphs
- Orientations of graphs with prescribed weighted out-degrees
- Strengthening \((a,b)\)-choosability results to \((a,b)\)-paintability
- Improved lower bounds on the number of edges in list critical and online list critical graphs
- The list-chromatic index of \(K_6\)
- Brooks' Theorem and Beyond
- Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
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)
