The main objective of our paper is the following *Connected List Coloring problem* introduced by Vising in 1999 [9].

Suppose we are given a graph *G*=(*V*, *E*) and a finite set *C* of *colors*. Agiven function *A* : *V*→ 2^{C} specifies for each vertex *v* ∈ *V* a subset *A*(*v*)⊆ *C* of admissible colors. Function *A* will be referred to as a *prescription*. Function : *V*→ *C* is called a *connected list coloring* (CLC) of graph *G*, if (*v*) ∈ *A*(*v*),∀*v* ∈ *V*, and for each color *i* ∈ *C* the subset of all identically colored vertices ^{–1}(*i*) specifies a connected subgraph of *G*.(The subgraph defined on the empty set of vertices is supposed to be connected.) Given an input *I* of the CLC problem, we wish either to find a CLC or to prove that it does not exist.

This problem is closely related to the problem of determining *sufficient conditions* for the existence of a CLC for a given input *I*=(*G*, *C*, *A*). The main question is: for which graphs and under which constraints on the lists of admissible colors does the desired coloring exist? In [9] this question was investigated from the viewpoint of constraints on the cardinality of lists. Let *A*_{min}=min_{v ∈V}|*A*(*v*)| and *A*_{max}=max_{v ∈V}|*A*(*v*)| be, respectively, ...

Start Free Trial

No credit card required