Pre-coloring extension for circular colorings
by
Douglas B. West
University of Illinois
Coauthors: Michael O. Albertson (Smith College)

A graph G is (k, d)-colorable if the vertices can be labeled with colors 1, ... , k such that adjacent vertices receive colors differing cyclically by at least d. In other works, uv in E(G) implies d <= |f(u)-f(v)| <= k-d in a (k, d)-coloring f; note that a (k, 1)-coloring is a proper k-coloring.

Let k, d, k', d' be positive integers with k'/d' > k/d, and let r=k'd-kd'. Let G be a (k, d)-colorable graph, and let P be a set of vertices in G such that the distance between any two vertices of P is at least \delta. We prove that if \delta >= 2\lceilkk'/(2r)\rceil, then every k'-coloring of P extends to a (k', d')-coloring of G. Furthermore, examples show that the distance requirement within P is nearly sharp when k'/d' and k/d differ by less than 1.

Date received: April 20, 2001