List precoloring extension in planar graphs

DOI10.1016/J.DISC.2011.03.007zbMATH Open1223.05062arXiv1006.5596OpenAlexW2053974194MaRDI QIDQ536235FDOQ536235

Authors: Joan P. Hutchinson, Michelle A. Lastrina, Maria Axenovich 

Publication date: 16 May 2011

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A celebrated result of Thomassen states that not only can every planar graph be colored properly with five colors, but no matter how arbitrary palettes of five colors are assigned to vertices, one can choose a color from the corresponding palette for each vertex so that the resulting coloring is proper. This result is referred to as 5-choosability of planar graphs. Albertson asked whether Thomassen's theorem can be extended by precoloring some vertices which are at a large enough distance apart in a graph. Here, among others, we answer the question in the case when the graph does not contain short cycles separating precolored vertices and when there is a "wide" Steiner tree containing all the precolored vertices.

Full work available at URL: https://arxiv.org/abs/1006.5596

Recommendations

• 5-list-coloring planar graphs with distant precolored vertices
• A note on planar 5-list colouring: Non-extendability at distance 4
• List colourings of planar graphs
• 3-list-coloring planar graphs of girth 5
• You can't paint yourself into a corner

zbMATH Keywords

planar graphslist-coloringAlbertson's conjecturecoloring extension

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Every planar graph is 5-choosable
• Color-critical graphs on a fixed surface
• Exponentially many 5-list-colorings of planar graphs
• Multicriterial graph problems with MAXMIN criterion
• List colourings of planar graphs
• You can't paint yourself into a corner
• Title not available (Why is that?)
• Dirac's map-color theorem for choosability
• Title not available (Why is that?)
• The colour theorems of Brooks and Gallai extended
• A note on planar 5-list colouring: Non-extendability at distance 4

Cited In (8)

• Flexibility of planar graphs -- sharpening the tools to get lists of size four
• Extending precolorings to distinguish group actions
• 5-list-coloring planar graphs with distant precolored vertices
• Exponentially many 5-list-colorings of planar graphs
• A note on planar 5-list colouring: Non-extendability at distance 4
• Precoloring Extension for 2‐connected Graphs
• Extending precolorings of subgraphs of locally planar graphs
• On list-coloring extendable outerplanar graphs

This page was built for publication: List precoloring extension in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q536235)