O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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 images : VC is called a connected list coloring (CLC) of graph G, if images(v) ∈ A(v),∀vV, and for each color iC the subset of all identically colored vertices images–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.

Start Free Trial

No credit card required