Analysis of Complex Networks

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→ 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, ...