Critically paintable, choosable or colorable graphs

DOI10.1016/J.DISC.2012.07.035MaRDI QIDQ713164zbMATH OpenOpenAlexFDO

Authors Ayesha Riasat, Uwe Schauz

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

critical graphgraph coloringgraphs on surfaceslist coloringpaintability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• List-color-critical graphs on a fixed surface
• Color-critical graphs on a fixed surface
• The colour theorems of Brooks and Gallai extended
• On list critical graphs
• On \((4,2)\)-choosable graphs

Cites work

• A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs
• Application of polynomial method to on-line list colouring of graphs
• Brooks' theorem via the Alon-Tarsi theorem
• Color-critical graphs and hypergraphs with few edges: a survey
• Color-critical graphs on a fixed surface
• Dirac's map-color theorem for choosability
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• Graphs on surfaces
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3232667 (Why is no real title available?)
• Mr. Paint and Mrs. Correct go fractional
• On a Lovász-type lemma, applied to Brooks' theorem for list-colouring
• On chromatic‐choosable graphs
• On constructive methods in the theory of colour-critical graphs
• On the minimal number of edges in color-critical graphs
• On-line list colouring of graphs
• The complexity of some graph colouring problems
• The last excluded case of Dirac's map‐color theorem for choosability

Cited in

(4)

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

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

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