# Some Concepts in List Coloring

## 1 Introduction

We consider finite, undirected simple graphs. For necessary definitions and notations we refer the reader to standard texts such as .

By a $`k`$–list assignment $`L`$ to a graph $`G`$ we mean a map which assigns to each vertex $`v`$ of $`G`$ a set $`L(v)`$ of size $`k`$. A list coloring for $`G`$ from $`L`$, or an $`L`$–coloring for short, is a proper coloring $`c`$, in which for each vertex $`v`$, $`c(v)`$ is chosen from $`L(v)`$. A graph $`G`$ is called $`k`$–choosable if it has a list coloring from any $`k`$–list assignment to it. The minimum number $`k`$ for which $`G`$ is $`k`$–choosable is called the list chromatic number of $`G`$ and is denoted by $`\chi _{\mathrm{}}(G)`$. In the following theorem all $`2`$–choosable graphs are characterized. Before we state the theorem it should be noted that the core of a graph is a subgraph which is obtained by repeatedly deleting a vertex of degree 1, until no vertex of degree 1 remains.

###### Theorem A

.  A connected graph is $`2`$–choosable, if and only if its core is either a single vertex, an even cycle, or $`\theta _{2,2,2r}`$, for some $`r1`$.

A graph $`G`$ is called uniquely $`k`$–list colorable, or U$`k`$LC for short, if it admits a $`k`$–list assignment $`L`$ such that $`G`$ has a unique $`L`$–coloring. This concept was introduced by Dinitz and Martin  and independently by Mahdian and Mahmoodian ( and ). A characterization of uniquely $`2`$–list colorable graphs follows.

###### Theorem B

.  A graph $`G`$ is not U$`2`$LC if and only if each of its blocks is either a cycle, a complete graph, or a complete bipartite graph.

It is easy to see that for each graph $`G`$ there exists a number $`k`$ such that $`G`$ is not U$`k`$LC. The minimum $`k`$ with this property is called the m–number of $`G`$ and is denoted by $`\text{m}(G)`$. It is shown in  that every planar graph has m–number at most $`5`$, and it is asked about the existence of planar graphs with m–number equal to $`5`$. We study uniquely list colorable graphs in Section 2, where we prove that every triangle–free uniquely $`(k+1)`$–colorable graph is uniquely $`k`$–list colorable. We also show that every planar graph has m–number at most $`4`$, so the answer to that question in  is negative.

In Section 3 we introduce list critical graphs and characterize $`3`$–list critical graphs. Finally we pose a conjecture about list critical graphs which is shown to be equivalent to the list coloring conjecture.

## 2 Uniquely list colorable graphs

In  one can find several examples of U$`k`$LC graphs, for some arbitrary positive integer $`k`$. In the following lemma we also introduce a class of U$`k`$LC graphs. In this way we relate uniquely list colorable graphs to uniquely colorable graphs.

###### Lemma 1

. Let $`G`$ be a uniquely colorable graph with chromatic number $`k+1`$, and $`c`$ be its unique $`(k+1)`$–coloring with color classes $`C_1,\mathrm{},C_{k+1}`$. If for each $`ik+1`$, $`|C_i|i1`$, then $`G`$ is a uniquely $`k`$–list colorable graph.

###### Proof.

We proceed by induction on $`k`$ and prove that there exists a $`k`$–list assignment to such graph $`G`$ using exactly $`k+1`$ colors, which induces a unique list coloring. For $`k=1`$ the result obviously holds. Let $`G`$ be a uniquely $`(k+1)`$–colorable graph as in the statement and $`k2`$. By induction $`GC_{k+1}`$ admits a $`(k1)`$–list assignment $`L^{}`$ which induces a unique list coloring and uses colors $`1,\mathrm{},k`$. For each $`vV(G)C_{k+1}`$, assign the list $`L(v)=L^{}(v)\{k+1\}`$ to $`v`$, and since $`|C_{k+1}|k`$, it is possible to assign some lists to $`C_{k+1}`$ such that $`_{vC_{k+1}}L(v)=\{k+1\}`$. Now it is easy to see that $`L`$ is the desired list assignment.  $`\mathrm{}`$

It is shown in  that for every $`k3`$, in a triangle–free uniquely $`k`$–colorable graph, each color class has at least $`k+1`$ vertices. Using this result, we obtain the following theorem.

###### Theorem 1

. Every triangle–free uniquely $`(k+1)`$–colorable graph is uniquely $`k`$–list colorable.

On the other hand in  it is shown that for each $`k2`$, there exists a uniquely $`k`$–colorable graph with arbitrary large girth. So by theorem above, for each $`k`$, there exists a U$`k`$LC graph with arbitrary large girth.

We need here a definition which is a generalization of the concept of a U$`k`$LC graph.

###### Definition 1

. Let $`G`$ be a graph and $`f`$ a be function from $`V(G)`$ to $``$. An $`f`$–list assignment $`L`$ to $`G`$ is a list assignment in which $`|L(v)|=f(v)`$ for each vertex $`v`$. The graph $`G`$ is called to be uniquely $`f`$–list colorable, or U$`f`$LC for short, if there exists an $`f`$–list assignment $`L`$ for it such that $`G`$ has a unique $`L`$–coloring.

By definition above, if $`G`$ is a U$`f`$LC graph, where $`f(v)=k`$ for each vertex $`v`$ of $`G`$, then $`G`$ in fact is a U$`k`$LC graph. To prove the next theorem, we need a relation which is proved in Truszczyński  and states that if $`G`$ is a uniquely $`k`$–colorable graph, then $`e(G)(k1)n(G)\left(\genfrac{}{}{0pt}{}{k}{2}\right).`$

###### Theorem 2

. If $`G`$ is a U$`f`$LC graph, then

$$\underset{vV(G)}{}f(v)n(G)+e(G).$$

###### Proof.

Suppose that $`L`$ is an $`f`$–list assignment to $`G`$ using colors $`1,2,\mathrm{},t`$, such that $`G`$ has a unique $`L`$–coloring. We construct a uniquely $`t`$–colorable graph $`G^{}`$ as follows. Let $`V(G)=\{v_1,\mathrm{},v_n\}`$ and $`K_t`$ is a complete graph on the vertex set $`\{w_1,\mathrm{},w_t\}`$. Now for $`G^{}`$ consider the union of $`G`$ and $`K_t`$ and add edges $`v_iw_j`$ where $`1in`$, $`1jt`$, and $`jL(v_i)`$.

Consider a $`t`$–coloring $`c`$ of $`G^{}`$. Without loss of generality we can assume that $`c(w_i)=i`$ for each $`1it`$. Since $`G`$ has a unique $`L`$–coloring, by construction of $`G^{}`$, $`c`$ is the only $`t`$–coloring of $`G^{}`$. So $`G^{}`$ is a uniquely $`t`$–colorable graph. On the other hand $`G^{}`$ has $`n(G)+t`$ vertices, and $`e(G)+\left(\genfrac{}{}{0pt}{}{t}{2}\right)+_{vV(G)}(tf(v))`$ edges. Therefore as mentioned above, we have

$$e(G)+\left(\genfrac{}{}{0pt}{}{t}{2}\right)+\underset{vV(G)}{}(tf(v))(n(G)+t)(t1)\left(\genfrac{}{}{0pt}{}{t}{2}\right)$$

and after simplification we obtain the result.  $`\mathrm{}`$

A natural question which arises here is that whether or not equality holds in Theorem 2? In the following proposition we give a positive answer to this question.

###### Proposition 1

. For every graph $`G`$, there exists $`f:V(G)`$ such that $`G`$ is U$`f`$LC and $`_{vV(G)}f(v)=n(G)+e(G)`$.

###### Proof.

We proceed by induction on the number of vertices of $`G`$. For $`n(G)=1`$ the statement is obvious. Consider a graph $`G`$ with $`n(G)2`$ and a vertex $`v`$ of $`G`$. By induction there exists $`f^{}:V(Gv)`$ and an $`f^{}`$–list assignment $`L^{}`$ to $`Gv`$ such that $`Gv`$ has a unique $`L^{}`$–coloring, and $`_{wV(Gv)}f(w)=n(Gv)+e(Gv)`$. Consider a color $`a`$ which is not used by $`L^{}`$, and define a list assignment $`L`$ to $`G`$ as follows.

$$L(w)=\{\begin{array}{cc}a\hfill & \mathrm{for}w=v\hfill \\ L^{}(w)\{a\}\hfill & \mathrm{for}wN(v)\hfill \\ L^{}(w)\hfill & \mathrm{otherwise}.\hfill \end{array}$$

It is easy to verify that $`G`$ has a unique $`L`$–coloring and that we have $`_{vV(G)}|L(v)|=n(G)+e(G)`$.  $`\mathrm{}`$

Although the proposition above shows that in Theorem 2 equality may hold, but it seems that if $`f(v)=k`$ for each vertex $`v`$, equality does not hold and we have $`e(G)>(k1)n(G)`$.

By definition every graph $`G`$ for $`k=\text{m}(G)1`$ is U$`k`$LCṠo by Theorem 2 we have the following.

###### Theorem 3

. For a graph $`G`$ let $`\overline{d}(G)`$ denote the average degree of $`G`$, i.e. $`\overline{d}(G)=2e(G)/n(G)`$. Then

$$\text{m}(G)\frac{\overline{d}(G)}{2}+2.$$

For example suppose that $`G`$ is a bipartite graph. We have $`\overline{d}(G)n(G)/2`$ so Theorem 3 implies $`\text{m}(G)n(G)/4+2`$. This bound can be improved to a logarithmic bound as we will show in Theorem 4, but first we need a lemma.

Let $`L`$ be a $`k`$–list assignment to a graph $`G`$ such that $`G`$ has a unique $`L`$–coloring $`c`$. For each vertex $`v`$ of $`G`$, all the elements of $`L(v)\{c(v)\}`$ must appear in $`N(v)`$, so if we denote by $`c_N(v)`$ the set of colors appearing in $`N(v)`$, then $`|c_N(v)|k1`$. In the following lemma we state a stronger result.

###### Lemma 2

. Suppose that $`G`$ is a U$`k`$LC graph, and $`L`$ is a $`k`$–list assignment to $`G`$ such that $`G`$ has a unique $`L`$–coloring $`c`$ with color classes $`C_1,\mathrm{},C_t`$ such that $`c(C_i)=\{i\}`$. There exist at least $`k1`$ classes containing a vertex $`v`$ with $`|c_N(v)|k`$.

###### Proof.

Without loss of generality suppose that for $`\mathrm{}k1`$, $`C_{\mathrm{}}`$ contains no vertex $`v`$ with $`|c_N(v)|k`$. Assume that $`uC_{k1}`$, $`i=c(v_0)`$, and $`jL(v_0)\{1,\mathrm{},k1\}`$. Suppose that $`G_{ij}`$ is the subgraph of $`G`$ induced on $`C_iC_j`$. Since for each vertex $`v`$ of the component of $`G_{ij}`$ containing $`v_0`$ we have $`|c_N(v)|=k1`$, it is implied that $`i,jL(v)`$. So we can interchange the colors $`i`$ and $`j`$ in this component to obtain a new $`L`$–coloring for $`G`$. This contradiction completes the proof.  $`\mathrm{}`$

It is shown in  that every non–$`k`$–choosable bipartite graph has more than $`2^{k1}`$ vertices. So by applying Lemma 2, we deduce the following theorem.

###### Theorem 4

. Let $`G`$ be a bipartite graph. Then $`\text{m}(G)2+\mathrm{log}_2n(G).`$

###### Proof.

Suppose that $`L`$ is a $`k`$–list assignment to $`G`$ such that $`G`$ has a unique $`L`$–coloring $`c`$. By Lemma 2, $`G`$ has a vertex $`v_0`$, such that there are at least $`k`$ colors appeared at $`N(v_0)`$ in $`c`$. Let $`G^{}`$ be the graph obtained from $`G`$, by duplicating $`v_0`$, i.e. adding a new vertex $`w`$ to $`G`$ and joining it to $`N(v_0)`$. Now assign to $`w`$ a list containing $`k`$ of the colors appeared at $`N(v_0)`$ in $`c`$, and the list $`L(v)`$ to each other vertex $`v`$ of $`G^{}`$. It is clear that $`G^{}`$ is a bipartite graph and it has no coloring from these lists, so it is not $`k`$–choosable. Hence $`n(G^{})>2^{k1}`$ vertices. This implies that $`n(G)2^{k1}`$, and so $`k1+\mathrm{log}_2n(G)`$. Now we obtain the desired relation by setting $`k=\text{m}(G)1`$.  $`\mathrm{}`$

In the remainder of this section we state some consequences of Theorems 2 and 3.

It is well known that a planar graph with $`n`$ vertices has at most $`3n6`$ edges. So the following theorem is an immediate consequence of Theorem 3.

###### Theorem 5

. For every planar graph $`G`$ we have $`\text{m}(G)4`$.

By Lemma 1 the planar graph shown in Figure 1 is a U$`3`$LC graph for which the inequalities in Theorem 3 and Theorem 5 turn to be equalities.

Furthermore we know that a triangle–free planar graph $`G`$, has at most $`2n(G)4`$ edges. So Theorem 3 implies that each triangle–free planar graph $`G`$ has m–number at most $`3`$. In the following proposition a stronger result is obtained.

###### Proposition 2

. If a plane graph has at most $`7`$ triangular faces, then $`\text{m}(G)3`$.

###### Proof.

Consider a U$`3`$LC plane graph $`G`$ with $`n`$ vertices, $`e`$ edges, $`f`$ faces, and $`t`$ triangular faces. We have $`2e4(ft)+3t=4ft`$, and by Euler formula $`f=2n+e`$, so $`t84n+2e`$. On the other hand Theorem 2 implies that $`e2n`$. So $`t8`$, as desired.  $`\mathrm{}`$

The following conjecture is about the structure of U$`3`$LC planar graphs which is motivated by the proposition above.

###### Conjecture 1

. Every U$`3`$LC planar graph has $`K_4`$ as a subgraph.

For another application of Theorem 2, we study line and total versions of uniquely list coloring.

A graph $`G`$ is called to be uniquely $`k`$–list edge colorable, if $`L(G)`$ is a uniquely $`k`$–list colorable graph. The edge m–number of $`G`$ is defined to be $`\text{m}(L(G))`$, and is denoted by $`\text{m}^{}(G)`$. It is straightforward to see that for each graph $`G`$, $`\overline{d}(L(G))\mathrm{\Delta }(L(G))2\mathrm{\Delta }(G)2`$. So using Theorem 3 we deduce the following.

###### Theorem 6

. For every graph $`G`$, we have $`\text{m}^{}(G)\mathrm{\Delta }(G)+1`$ and if $`\text{m}^{}(G)=\mathrm{\Delta }(G)+1`$ then $`G`$ is a regular graph.

Note that in Theorem 6 it is shown that if $`G`$ is not a regular graph, then $`\text{m}(G)\mathrm{\Delta }(G)`$. So in this case $`\text{m}(G)\chi (G)`$.

## 3 List critical graphs

In this section we introduce a concept of list critical graphs and we state some results concerning it.

###### Definition 2

. A graph $`G`$ is called $`\chi _{\mathrm{}}`$–critical if for each proper subgraph $`H`$ of it we have $`\chi _{\mathrm{}}(H)<\chi _{\mathrm{}}(G)`$.

We sometimes refer to a $`\chi _{\mathrm{}}`$–critical graph $`G`$ as a $`k`$–list critical graph, where $`k=\chi _{\mathrm{}}(G)`$. It can easily be verified that the only connected $`2`$–list critical graph is $`K_2`$, odd cycles are $`3`$–list critical, and the complete graph $`K_k`$ is $`k`$–list critical.

Obviously every graph $`G`$ contains a $`\chi _{\mathrm{}}`$–critical subgraph $`H`$ such that $`\chi _{\mathrm{}}(H)=\chi _{\mathrm{}}(G)`$, and by an argument similar to critical graphs, $`\delta (G)\chi _{\mathrm{}}(G)1`$. On the other hand there exists some differences between critical graphs and list critical graphs. For example it is well known that every critical graph is $`2`$–connected. In Figure 2 we have given an example of a $`3`$–list critical graph which is not $`2`$–connected.

In the next theorem $`3`$–list critical graphs are characterized.

###### Theorem 7

. A graph is $`3`$–list critical if and only if it is either an odd cycle, two even cycles with a path joined them, $`\theta _{r,s,t}`$ where $`r`$, $`s`$, $`t`$ have the same parity, and at most one of them is $`2`$, or $`\theta _{2,2,2,2r}`$ where $`r1`$.

###### Proof.

By use of Theorem A, it is easy to see that all the graphs listed in the statement are $`3`$–list critical.

For the converse suppose that $`G`$ is a $`3`$–list critical graph. If $`G`$ is $`2`$–connected, by a theorem of Whitney  $`G`$ has an ear decomposition $`K_2P^1\mathrm{}P^q`$. If $`q4`$, deleting an edge of $`P^q`$, yields a non–$`2`$–choosable graph, which contradicts the $`3`$–list criticality of $`G`$. So $`q3`$ and we consider the following three cases.

* If $`q=1`$, $`G`$ is a cycle, and so it is an odd cycle.
* If $`q=2`$, $`G=\theta _{r,s,t}`$. In this case by deleting each edge of $`G`$, we obtain a graph whose core is a cycle, and since this cycle must be even, the numbers $`r`$, $`s`$, and $`t`$ have the same parity. Now if at least two of $`r`$, $`s`$, and $`t`$ are equal to $`2`$, we have $`\chi _{\mathrm{}}(G)=2`$, a contradiction.
* The last case is $`q=3`$. By deleting each edge of $`G`$ we obtain a graph whose core is a $`\theta _{r,s,t}`$, and since this graph must be $`2`$–choosable, we have $`r=s=2`$ and $`t`$ is an even number. Now by case analysis, it is easy to see that $`G=\theta _{2,2,2,2\mathrm{}}`$.

On the other hand if $`G`$ is not $`2`$–connected, we consider two end–blocks $`B_1`$ and $`B_2`$ of $`G`$. Since $`\delta (G)2`$ each of $`B_1`$ and $`B_2`$ has a cycle. So $`G`$ has a subgraph $`H`$ which is composed of two edge–disjoint cycles joined to each other by a path (possibly of length zero). We know that $`\chi _{\mathrm{}}(H)=3`$, and so by $`\chi _{\mathrm{}}`$–criticality of $`G`$, $`G`$ has no edge outside $`H`$, i.e. $`G=H`$. Hence $`G`$ satisfies the statement.  $`\mathrm{}`$

Suppose that $`G`$ is a $`k`$–list critical graph, and $`L`$ is a $`k`$–list assignment to $`G`$. Consider a vertex $`v`$ in $`G`$ and a color $`aL(v)`$. Assign to each vertex $`u`$ in $`Gv`$ the list $`L(u)\{a\}`$. Since $`Gv`$ is $`(k1)`$–choosable, it has a coloring from the assigned lists, and one can extend this coloring to an $`L`$–coloring of $`G`$ by assigning the color $`a`$ to $`v`$. So there exists an $`L`$–coloring for $`G`$ in which $`v`$ takes $`a`$.

As mentioned in the previous paragraph, every $`k`$–list critical graph has at least $`k`$ colorings from each $`k`$–list assignment so every $`k`$–list critical graph has m–number at most $`k`$.

A graph $`G`$ is called to be edge $`k`$–choosable, if the graph $`L(G)`$ is $`k`$–choosable, and the list chromatic index of $`G`$ written $`\chi _{\mathrm{}}^{}(G)`$ is defined to be $`\chi _{\mathrm{}}(L(G))`$. As in the case of defining $`\chi ^{}`$–critical graphs, one can define a $`\chi _{\mathrm{}}^{}`$–critical graph $`G`$ to be a graph in which for each proper subgraph $`H`$, $`\chi _{\mathrm{}}^{}(H)<\chi _{\mathrm{}}^{}(G)`$. We recall here the well known List Coloring Conjecture (LCC), which first appeared in print in .

###### Conjecture

.  Every graph $`G`$ satisfies $`\chi _{\mathrm{}}^{}(G)=\chi ^{}(G)`$.

Suppose that $`G`$ is a counterexample to the LCC with minimum number of edges. So for each edge $`uv`$ of $`G`$ we have $`\chi _{\mathrm{}}^{}(Guv)=\chi ^{}(Guv)`$, and since $`\chi ^{}(Guv)\chi ^{}(G)<\chi _{\mathrm{}}^{}(G)`$, we conclude that $`\chi _{\mathrm{}}^{}(Guv)=\chi _{\mathrm{}}^{}(G)1`$. This means that $`G`$ is a $`\chi _{\mathrm{}}^{}`$–critical graph and therefore $`\chi _{\mathrm{}}^{}`$–critical graphs may be useful to attack the LCC.

In the study of $`\chi _{\mathrm{}}^{}`$–critical graphs we have lead to the following conjecture.

###### Conjecture 2

. Every $`\chi _{\mathrm{}}^{}`$–critical graph is $`\chi ^{}`$–critical.

###### Proposition 3

. The conjecture above is equivalent with the LCC, while its converse is implied by the LCC.

###### Proof.

It is straight forward to check that the list coloring conjecture implies Conjecture 2 and its converse. On the other hand suppose that Conjecture 2 is true, and $`G`$ is a counterexample to the list coloring conjecture with minimum number of edges. As mentioned above $`G`$ is $`\chi _{\mathrm{}}^{}`$–critical, and by Conjecture 2, it is $`\chi ^{}`$–critical. By removing an arbitrary edge $`uv`$ from $`G`$ we obtain a graph for which the list coloring conjecture holds. So $`\chi _{\mathrm{}}^{}(Guv)=\chi ^{}(Guv)`$, and this means that $`\chi _{\mathrm{}}^{}(G)1=\chi ^{}(G)1`$, a contradiction.  $`\mathrm{}`$

In  it is proved that every bipartite multigraph fulfills the LCC. On the other hand we know that the only bipartite $`\chi ^{}`$–critical graphs are stars. So the following theorem is implied by a similar argument as in the previous paragraph, the only bipartite $`\chi _{\mathrm{}}^{}`$–critical graphs are stars.

## Acknowledgements

The authors wish to thank Professor E. S. Mahmoodian and R. Tusserkani for their helpful comments. They are indebted to the Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran for their support.

eslahchi@karun.ipm.ac.ir   
ghebleh@karun.ipm.ac.ir   
hhaji@karun.ipm.ac.ir