Brooks' theorem via the Alon-Tarsi theorem

DOI10.1016/j.disc.2010.07.019zbMath1222.05061arXiv0905.3475WikidataQ57601408 ScholiaQ57601408MaRDI QIDQ712277

Uwe Schauz, Jan Hladký, 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 coloring; Brooks' theorem; Alon-Tarsi method

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

Related Items

List-Coloring Claw-Free Graphs with $\Delta-1$ Colors, The tournament scheduling problem with absences, Application of polynomial method to on-line list colouring of graphs, Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker, Orientations of graphs with prescribed weighted out-degrees, On two generalizations of the Alon-Tarsi polynomial method, Critically paintable, choosable or colorable graphs, Proof of the list edge coloring conjecture for complete graphs of prime degree, Dynamic coloring parameters for graphs with given genus, On a Lovász-type lemma, applied to Brooks' theorem for list-colouring, Improved lower bounds on the number of edges in list critical and online list critical graphs, Beyond degree choosability, Strengthening \((a,b)\)-choosability results to \((a,b)\)-paintability, The list-chromatic index of \(K_6\), Brooks' theorem on powers of graphs, Partial Online List Coloring of Graphs, Brooks' Theorem and Beyond

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
• Circular degree choosability
• Colorings and orientations of graphs
• Three short proofs in graph theory
• The colour theorems of Brooks and Gallai extended
• Mr. Paint and Mrs. Correct
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• On two questions about circular choosability
• Circular choosability via combinatorial Nullstellensatz
• Star chromatic number
• On a four-colour theorem.
• Combinatorial Nullstellensatz
• Circular choosability of graphs
• Circular chromatic number: A survey