Dirac's map-color theorem for choosability
From MaRDI portal
Publication:4719323
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
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
