You can't paint yourself into a corner

DOI10.1006/jctb.1998.1827zbMath0910.05026OpenAlexW1985316243MaRDI QIDQ1272489

Michael O. Albertson

Publication date: 9 April 1999

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

Full work available at URL: https://semanticscholar.org/paper/0c798585b3e306ae03567a2f92a675239171a4c4

zbMATH Keywords

distancechromatic numbercliqueplanar graph\(k\)-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (27)

Noncontextual coloring of orthogonality hypergraphs ⋮ Extending precolorings of subgraphs of locally planar graphs ⋮ The number of defective colorings of graphs on surfaces ⋮ Precoloring extension involving pairs of vertices of small distance ⋮ Extending precolorings to distinguish group actions ⋮ Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings ⋮ Hyperbolic families and coloring graphs on surfaces ⋮ 5-list-coloring planar graphs with distant precolored vertices ⋮ Extension from precoloured sets of edges ⋮ Distance constraints in graph color extensions ⋮ Flexibility of triangle‐free planar graphs ⋮ Brooks' theorem with forbidden colors ⋮ On list-coloring outerplanar graphs ⋮ Extending precolourings of circular cliques ⋮ 5-choosability of graphs with crossings far apart ⋮ Flexibility of planar graphs -- sharpening the tools to get lists of size four ⋮ List precoloring extension in planar graphs ⋮ Extending precolorings to circular colorings ⋮ Precoloring extension of co-Meyniel graphs ⋮ Every graph \(G\) is Hall \(\Delta(G)\)-extendible ⋮ Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies ⋮ Precoloring extension forK₄-minor-free graphs ⋮ Extending graph colorings ⋮ Precoloring extension for 2-connected graphs with maximum degree three ⋮ Extending colorings of planar graphs ⋮ Extending partial 5-colorings and 6-colorings in planar graphs ⋮ On Baire measurable colorings of group actions

Cites Work

• List colourings of planar graphs
• Precoloring extension. I: Interval graphs
• The non-existence of colorings
• Geometric coloring theory
• Five-coloring maps on surfaces
• Five-coloring graphs on the torus
• Every planar graph is 5-choosable
• Color-critical graphs on a fixed surface
• Locally Planar Toroidal Graphs are 5-Colorable
• Precoloring Extension III: Classes of Perfect Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: You can't paint yourself into a corner