Trouble understanding the notion of choosability in graph theory (colorings)

89 Views Asked by At

I am going through some notes on graph theory, and the notion of list coloring is introduced. A specific list coloring on a graph G is

List colouring: a map $c:V(G) \rightarrow \mathbb{N}$ such that $c(v) \neq c(u)$ whenever $uv \in E(G)$, and where $\forall v\in V$, $c(v)\in L(v)$, which is a specified set of colors allowed for the vertex $v$.

Now there is an associated notion of choosability, which is like the chromatic number $\chi(G)$

$\chi_l(G) = \text{max}\{ k | \exists \ \text{a list coloring whenever} \ |L(v)| \geq k \ \forall v \in V(G) \}$

Apparently, $\chi_l(G) \geq \chi(G)$

but I cannot understand why!

My thought would be that the worst case scenario for the function $L$ is precisely when you allow the same set of colors for all of the vertices. And then you will never do worse that $\chi_l(G) = \chi(G)$. i.e. a there is certainly always a coloring when we allow the same $\chi(G)$ colors for each vertex, but if you have $|L(v)|=1$ for each vertex, but assign the colors appropriately, you can do it with $|L(G)|=1$. Of course, the 'whenever' does not apply, but hopefully this explains why I think $\chi_l(G)=\chi(G)$!

1

There are 1 best solutions below

3
On BEST ANSWER

You say you don't understand why $\chi_\ell(G)\ge\chi(G)$. The reason why $\chi_\ell(G)\ge\chi(G)$ is because, if $G$ is $k$-list-colorable, then $G$ is also $k$-colorable in the ordinary sense, by simply assigning the same list of colors to each vertex.

I think you really meant to say that you don't understand how $\chi_\ell(G)$ can be greater than $\chi(G)$. It's because your intuition, that "all lists the same" is the hardest case, is wrong. It's true that "pairwise disjoint lists" is the easiest case, but "identical lists" is not necessarily the hardest case. Here is an example.

Let $G$ be a graph with vertices $u,v,w,x,y,z$ and edges $uv,vw,wx,xy,yz,zu,vy$. This graph is obviously $2$-colorable; if we assign the list $\{1,2\}$ to each vertex, we can give color $1$ to vertices $u,w,y$ and color $2$ to vertices $v,x,z$. But suppose we assign a list of two colors to each vertex in the following way:

$u\to2,3$
$v\to1,2$
$w\to1,3$
$x\to2,3$
$y\to1,2$
$z\to1,3$

Can you get a proper coloring by choosing colors from these lists?

In fact, there are bipartite ($2$-colorable) graphs with arbitrarily large list coloring number. For instance, the complete bipartite graph $K_{n,n^n}$ is not $n$-list colorable. To see this, on the left side, assign pairwise disjoint lists of $n$ colors to the $n$ vertices; on the right side see to it that, no matter how you choose one color from each of those $n$ lists, the set of chosen colors is the list assigned to some vertex on the right.