Extending precolorings to circular colorings

Fix positive integers k', d', k, d such that k'/d'>k/d >= 2. If P is a set of vertices in a (k, d)-colorable graph G, and any two vertices of P are separated by distance at least 2 [kk'/(2(k'd-kd'))], then every coloring of P with colors in Z(k') extends to a (k',d')-coloring of G. If k'd-kd'=1 and [k'/d']=[k/d], then this distance threshold is nearly sharp. The proof of this includes showing that up to symmetry, in this case there is only one (k', d')-coloring of the canonical (k, d)-colorable graph G(k,d). (C) 2005 Elsevier Inc. All rights reserved.