From the plane to higher surfaces

DOI10.1016/j.jctb.2012.03.001zbMath1244.05075OpenAlexW2026401558WikidataQ56926580 ScholiaQ56926580MaRDI QIDQ444375

Carsten Thomassen, Ken-ichi Kawarabayashi

Publication date: 14 August 2012

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.2012.03.001

zbMATH Keywords

decompositionplanar graphs3-colorabilityhigher surfaceslist-coloring

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, Boxicity and topological invariants, Box representations of embedded graphs, Islands in Graphs on Surfaces, Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs, Colouring Planar Graphs With Three Colours and No Large Monochromatic Components

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• List colourings of planar graphs
• Locally planar graphs are 5-choosable
• Decomposing a planar graph of girth 5 into an independent set and a forest
• On acyclic colorings of planar graphs
• Five-coloring maps on surfaces
• Every planar graph is 5-choosable
• The four-colour theorem
• The chromatic number of a graph of girth 5 on a fixed surface
• A short list color proof of Grötzsch's theorem
• Partitioning into graphs with only small components
• Acyclic colorings of locally planar graphs
• Decomposing a planar graph into an independent set and a 3-degenerate graph
• Coloring with no 2-colored \(P_4\)'s
• 3-list-coloring planar graphs of girth 5
• Decomposing a planar graph into degenerate graphs
• Star Coloring and Acyclic Coloring of Locally Planar Graphs
• Every Planar Map is Four Colorable
• Coloring graphs with fixed genus and girth
• Algorithms – ESA 2004
• Acyclic colorings of planar graphs