List circular backbone colouring
Frederic Havet, Andrew King
Abstract
A natural generalization of graph colouring involves taking colours
from a metric space and insisting that the endpoints of an edge
receive colours separated by a minimum distance dictated by properties
of the edge. In the q-backbone colouring problem, these
minimum distances are either q or 1,
depending on whether or not the edge is in the backbone. In
this paper we consider the list version of this problem, with
particular focus on colours in ℤp
- this problem is closely related to the problem of circular
choosability. We first prove that the list circular
q-backbone chromatic number of a graph is bounded by
a function of the list chromatic number. We then consider the more
general problem in which each edge is assigned an individual distance
between its endpoints, and provide bounds using the Combinatorial
Nullstellensatz. Through this result and through structural
approaches, we achieve good bounds when both the graph and the
backbone belong to restricted families of graphs.
Full Text: PDF PostScript