Dirac's map-color theorem for choosability

DOI<327::AID-JGT2>3.0.CO;2-B 10.1002/(SICI)1097-0118(199912)32:4<327::AID-JGT2>3.0.CO;2-BzbMath0941.05025OpenAlexW4243022563MaRDI QIDQ4719323

Thomas Böhme, Bojan Mohar, Michael Stiebitz

Publication date: 3 August 2000

Full work available at URL: https://doi.org/10.1002/(sici)1097-0118(199912)32:4<327::aid-jgt2>3.0.co;2-b

zbMATH Keywords

colouringchoosabilitycritical graphchoice numberHeawood number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

The choice number versus the chromatic number for graphs embeddable on orientable surfaces ⋮ The 4-choosability of toroidal graphs without intersecting triangles ⋮ Coloring vertices and faces of locally planar graphs ⋮ Improper choosability of graphs of nonnegative characteristic ⋮ 5-list-coloring planar graphs with distant precolored vertices ⋮ A new sufficient condition for a toroidal graph to be 4-choosable ⋮ Beyond degree choosability ⋮ Coloring Eulerian triangulations of the Klein bottle ⋮ Five-list-coloring graphs on surfaces. III: One list of size one and one list of size two ⋮ Phase transition of degeneracy in minor-closed families ⋮ Every toroidal graph is acyclically 8-choosable ⋮ Degree choosable signed graphs ⋮ Locally planar graphs are 5-choosable ⋮ Entire coloring of graphs embedded in a surface of nonnegative characteristic ⋮ List precoloring extension in planar graphs ⋮ Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs ⋮ Coloring face hypergraphs on surfaces ⋮ Critically paintable, choosable or colorable graphs ⋮ A list version of Dirac's theorem on the number of edges in colour-critical graphs ⋮ Distributed coloring in sparse graphs with fewer colors ⋮ Coloring face-hypergraphs of graphs on surfaces ⋮ A map colour theorem for the union of graphs ⋮ Toroidal graphs containing neither nor 6‐cycles are 4‐choosable

Cites Work

• List colourings of planar graphs
• Every planar graph is 5-choosable
• The colour theorems of Brooks and Gallai extended
• Color-critical graphs on a fixed surface
• Map Colour Theorems Related To the Heawood Colour Formula
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• Short Proof of a Map-Colour Theorem
• A Six Color Problem
• SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
• Bestimmung der Maximalzahl der Nachbargebiete auf nicht-orientierbaren Flächen

This page was built for publication: Dirac's map-color theorem for choosability