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?


[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