List precoloring extension in planar graphs

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

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2011-06, Vol.311 (12), p.1046-1056
Main Authors: Axenovich, Maria, Hutchinson, Joan P., Lastrina, Michelle A.
Format: Article
Language:English
Subjects:
Albertson’s conjecture
Coloring
Coloring extension
Graphs
List-coloring
Lists
Mathematical analysis
Planar graphs
Theorems
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2011.03.007