Extending
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. Albertson asks
for the following extension to graphs where pairs of vertices in W may be adjacent.
Conjecture:
Suppose that we're given a
planar graph G, a set
W of K_2's of distance at least d from each other (with d between 4 and 9), and a 5-coloring of the vertices of W.
Does there exist a 5-coloring of G
that extends the 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