## 12.4 A Parameterized Class of Subproblems of the CLC Problem

To perform the complexity analysis of the CLC problem, it is convenient to represent its input in the form of graph *Ĝ* = (*V*, *C*; *E*, *E*_{A}) depicted in Figure 12.2. The set of vertices of this graph consists of two parts: *V* and *C*; set *V* will be referred to as the *left part* of graph *Ĝ*, while *C* will be called the *right part*. The set of edges will also consist of two parts: *E* and *E*_{A}; the edges from *E* connect vertices in the left part, while the edges from *E*_{A} connect parts *V* and *C* (i.e., constitute a bipartite subgraph of *Ĝ*); an edge (*v*, *i*) belongs to *E*_{A} iff i ∈ *A*(*v*) (i.e., color *i* is admissible for vertex *v*).

The complexity of this problem will depend significantly on four parameters of graph *Ĝ*: *T*, Δ_{V}, Δ_{V,C}, Δ_{C,V}.

**Figure 12.2** Graph *Ĝ* defining an example of the CLC problem.

The first parameter *T* defines the *type* of graph *G*. We will distinguish between two types of graphs, depending on whether *G* is acyclic or not. Respectively, *T* will take only two values: 0 and ∞; *T* = 0 denotes the case of an acyclic graph *G*; otherwise *T* = ∞.

The second parameter Δ_{V} denotes the maximum vertex degree of graph *G* (where we take into account only the edges from *V* to *V*).

The third parameter Δ_{V,C} denotes the maximum vertex degree in *V* with respect to edges from *E*_{A}. It corresponds to the maximum cardinality of lists *A*(*v*).

Finally, the fourth parameter ...