Extending
List-5-Colorings of Planar Graphs
A common approach to coloring graphs is to try to extend colorings
of subgraphs. Carsten Thomassen [T] posed the following problem:
Suppose that we are given a planar graph G, a subset W of vertices such that the minimum
distance between vertices in W
is at least 100, and a 5-coloring of W. Is there an extension of this
partial coloring to a 5-coloring of G?
A solution to this problem was given by Albertson [A], who showed that
the coloring exists for all planar G
and subsets W where the
minimum distance between vertices in W
is at least 4, and that 4 was the best possible value.
A list-assignment L gives
a list of colors available at each vertex. Commonly the size k of the list is independent on the
vertices, and we talk about a k-list
assignment. An L-coloring
assigns each vertex one of the colors in its list. Usually we want proper colorings, so that adjacent
vertices receive distinct colors. The
list-chromatic number is the smallest k such that every k-list assignment L has a proper L-coloring. Obviously, the list
chromatic number is greater than or equal to the chromatic number,
since the latter is the special case that all vertices get lists 1,...,k.
Albertson asks for the following extension of his result to list
colorings.
Conjecture:
Suppose that we're given a
planar graph G, a set
W of vertices distance at least d from
each other (with d=4?), a list-assignment of 5 colors for each
vertex, and a partial list coloring of the vertices of W.
Does there exist a list-5-coloring of
G
that extends the list-5-coloring of
W?
References:
[T] C. Thomassen. Color-critical graphs on a fixed surface, J. Combin. Theory. Ser. B 70 (1997) 67-100/
Submitted by: Dan Archdeacon, Dept. of Math.
and Stat.,
Send comments to dan.archdeacon@uvm.edu
December 2003