How to find List Chromatic Number of planar graphs

Question

I want to know how we can find the list chromatic number of planar graphs,

Suppose we have graph $G= K_{3}$. Then its chromatic number is $3$, but what is the list chromatic number of $K_{3}$?

Anybody knows the answer or how we calculate it?

Answer 1

In general, calculating the list chromatic number for a graph is difficult. For the complete graph $K_3$, it is easy though if we make a few easy observations.

Let $G$ be a simple graph and let $\chi_\ell(G)$ denote its list chromatic number. Then $$\chi(G)\leq\chi_\ell(G)$$ since we can think of a proper $k$-coloring as a proper list coloring where each list is the set $\{1,2,...,k\}$.

Furthermore, $$\chi_\ell(G)\leq\Delta(G)+1$$ since if we have any set of lists, each with $\Delta(G)+1$ colors, we can use a greedy coloring to color each vertex. Having more than $\Delta(G)$ colors guarantees that at each step of the algorithm, we have a color to use. Thus we have $$\chi(G)\leq\chi_\ell(G)\leq\Delta(G)+1.$$ Applying this formula to $K_3$ yeilds $$3\leq\chi_\ell(K_3)\leq 3,$$ or $$\chi_\ell(K_3)=3.$$