## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## 12.2 The Connected List Coloring Problem

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→ 2C specifies for each vertex vV a subset A(v)⊆ C of admissible colors. Function A will be referred to as a prescription. Function : VC is called a connected list coloring (CLC) of graph G, if (v) ∈ A(v),∀vV, and for each color iC 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 Amin=minvV|A(v)| and Amax=maxvV|A(v)| be, respectively, ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required