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?


[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/

Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu

December 2003