**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: **

[A] M. Albertson, You can't paint
yourself into a corner, J. of
Combin. Theory. Ser B 73
(1998) 189-194.

[T] C. Thomassen. Color-critical graphs on a fixed surface, J. Combin. Theory. Ser. B 70 (1997) 67-100/

[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