Extending precolorings of subgraphs of locally planar graphs

DOI10.1016/j.ejc.2003.06.005zbMath1050.05044OpenAlexW1979274983MaRDI QIDQ1883295

Joan P. Hutchinson, Michael O. Albertson

Publication date: 4 October 2004

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2003.06.005

zbMATH Keywords

surfacewidthembedded graphlocally planar graphsnice cycle lemmaprecolorings of subgraphs

Mathematics Subject Classification ID

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

Related Items (11)

Extending precolorings to distinguish group actions ⋮ Coloring vertices and faces of locally planar graphs ⋮ Hyperbolic families and coloring graphs on surfaces ⋮ Distance constraints in graph color extensions ⋮ Flexibility of planar graphs -- sharpening the tools to get lists of size four ⋮ Extending precolorings to circular colorings ⋮ Every graph \(G\) is Hall \(\Delta(G)\)-extendible ⋮ Unnamed Item ⋮ Precoloring extension forK₄-minor-free graphs ⋮ Precoloring extension for 2-connected graphs with maximum degree three ⋮ Some Conjectures and Questions in Chromatic Topological Graph Theory

Cites Work

• Unnamed Item
• Graph color extensions: When Hadwiger's conjecture and embeddings help
• You can't paint yourself into a corner
• Five-coloring maps on surfaces
• The four-colour theorem
• Color-critical graphs on a fixed surface
• Extending colorings of locally planar graphs
• Disjoint paths, planarizing cycles, and spanning walks
• A Five-Color Theorem for Graphs on Surfaces
• Locally Planar Toroidal Graphs are 5-Colorable
• Every planar map is four colorable
• The Independence Ratio and Genus of a Graph
• Graph colorings with local constraints -- a survey

This page was built for publication: Extending precolorings of subgraphs of locally planar graphs