Critically paintable, choosable or colorable graphs

DOI10.1016/j.disc.2012.07.035zbMath1252.05070OpenAlexW2015381291MaRDI QIDQ713164

Uwe Schauz, Ayesha Riasat

Publication date: 26 October 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2012.07.035

zbMATH Keywords

graph coloringlist coloringcritical graphgraphs on surfacespaintability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (3)

Improved lower bounds on the number of edges in list critical and online list critical graphs ⋮ Proof of the list edge coloring conjecture for complete graphs of prime degree ⋮ Characterization of \((2m,m)\)-paintable graphs

Cites Work

• Application of polynomial method to on-line list colouring of graphs
• Mr. Paint and Mrs. Correct go fractional
• A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs
• Brooks' theorem via the Alon-Tarsi theorem
• On constructive methods in the theory of colour-critical graphs
• The complexity of some graph colouring problems
• On the minimal number of edges in color-critical graphs
• Color-critical graphs on a fixed surface
• On a Lovász-type lemma, applied to Brooks' theorem for list-colouring
• On-line list colouring of graphs
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• On chromatic‐choosable graphs
• Dirac's map-color theorem for choosability
• The last excluded case of Dirac's map‐color theorem for choosability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Critically paintable, choosable or colorable graphs