Locally planar graphs are 5-choosable

DOI10.1016/j.jctb.2008.01.003zbMath1187.05030OpenAlexW2045237424MaRDI QIDQ958683

Matt DeVos, Ken-ichi Kawarabayashi, Bojan Mohar

Publication date: 8 December 2008

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2008.01.003

zbMATH Keywords

surfacechoosabilitylist coloringedge-widthlocally planar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items

Hyperbolic families and coloring graphs on surfaces, Coloring Eulerian triangulations of the Klein bottle, Weak degeneracy of planar graphs and locally planar graphs, Algorithms for the edge-width of an embedded graph, On-line DP-coloring of graphs, Asymptotic enumeration and limit laws for graphs of fixed genus, From the plane to higher surfaces, 2- and 3-factors of graphs on surfaces, Toroidal grid minors and stretch in embedded graphs, Locally planar graphs are 2-defective 4-paintable, Some Conjectures and Questions in Chromatic Topological Graph Theory, Distributed coloring in sparse graphs with fewer colors, Unnamed Item, Locally planar graphs are 5-paintable

Cites Work

• Unnamed Item
• List colourings of planar graphs
• Graph minors. VII: Disjoint paths on a surface
• The complexity of planar graph choosability
• Five-coloring maps on surfaces
• Coloring graphs without short non-bounding cycles
• Every planar graph is 5-choosable
• The four-colour theorem
• Color-critical graphs on a fixed surface
• The chromatic number of a graph of girth 5 on a fixed surface
• Graph minors. XIII: The disjoint paths problem
• Graph Theory and Probability
• Every Planar Map is Four Colorable
• Graph colorings with local constraints -- a survey
• Dirac's map-color theorem for choosability