A proper coloring of a graph is an assignment of colors to vertices of a graph such that no two adjacent vertices receive the same color. A graph is k-colorable if it can be properly colored with k colors. For example, the famous Four Color Theorem states that “Evey planar graph is 4-colorable“. This is tight, since a complete graph on four vertices is 4-colorable but not 3-colorable. Deciding if a graph is 3-colorable is NP-hard. It is natural to ask which planar graphs are 3-colorable.

Grotzsch’s Theorem :Every triangle-tree planar graph is 3-colorable.

Dvorak, Kawarabayashi and Thomas [DKT ’08] presented a very short proof of Grotzsch’s theorem and a linear-time algorithm for 3-coloring such graphs.

Given a graph and given a set L(v) of colors for each vertex v, a list coloring is a proper coloring such that every vertex v is assigned a color from the list L(v). A graph is k-list-colorable (or k-choosable) if it has a proper list coloring no matter how one assigns a list of k colors to each vertex.

If a graph is k-choosable then it is k-colorable (set each L(v) = {1,…k}). But the converse is not true. Following is a bipartite graph (2-colorable) that is not 2-choosable (corresponding lists are shown).

A graph is k-degenerate if each non-empty subgraph contains a vertex of degree at most k. The following fact is easy to prove by induction :

Exercise :A k-degenerate graph is (k+1)-choosable

Are there k-degenerate graphs that are k-choosable ? Following are some known results and open problems :

- Every bipartite planar graph is 3-choosable [Alon & Tarsi ’92]. It is easy to prove that every bipartite planar graph is 3-degenerate.
- Every planar is 5-choosable [Thomassen ’94]. Note that every planar graph is 5-degenerate. There are planar graphs which are not 4-choosable [Voigt ’93].
- Every planar graph of girth at least 5 is 3-choosable. This implies grotzsch’s theorem in a very cute way [Thomassen ’03]. There are planar graphs of girth 4 which are not 3-choosable [Voigt ’95].

Open Problems :

- There is a conjecture stating
“Every 3-colorable planar graph is 4-choosable”. Prove or disprove this conjecture. A positive answer implies four color theorem !!- Another open problem (I learnt this problem from Robin Thomas‘s course on Graph Minors in Spring’2008) is
“Find a linear-time algorithm to 3-list-color planar graphs of girth 5″. Thomassen’s Proof [Thomassen ’03] gives a quadratic algorithm. I could not convert his proof into a linear-time algorithm. Probably it requires a new proof. It might be possible to get an algorithm using the data structures of [KK’03].

**References :**

**[Alon & Tarsi ’92]**N. Alon, M. Tarsi:**Colorings and orientations of graphs.***Combinatorica*12(2): 125-134 (1992)**[Thomassen ’94]**C. Thomassen:**Every Planar Graph Is 5-Choosable.***J. Comb. Theory, Ser. B*62(1): 180-181 (1994)**[Voigt ’93]**M. Voigt:**List colourings of planar graphs.***Discrete Mathematics*120(1-3): 215-219 (1993)**[Thomassen ’03]**C. Thomassen:**A short list color proof of Grötzsch’s theorem.***J. Comb. Theory, Ser. B*88(1): 189-192 (2003)**[Voigt ’95]**M. Voigt :**A not 3-choosable planar graph without 3-cycles.***Discrete Mathematics*146(1-3): 325-328 (1995)**[DKT ’08]**Z. Dvorak and K. Kawarabayashi and R. Thomas :**Three-coloring triangle-free planar graphs in linear time.***SODA 2009*.**[KK’03]**Lukasz Kowalik, Maciej Kurowski:**Short path queries in planar graphs in constant time.***STOC 2003*: 143-148

Can you explain the difference between k-list colorable and k-colorable? does k-colorable imply k-list colorable or vice-versa?

For k-choosability, one has to choose the colors from the lists L(v) at each vertex. This constraint is not there for k-colorability. If a graph is k-choosable then it is k-colorable because we can simply set each L(v) = {1,…k}. But the converse is not true. The bipartite graph shown in the post is a counterexample. In this example, there is no way to 2-color the bipartite graph choosing the colors from the lists shown. We know that every bipartite graph is 2-colorable.

On the first Open problem: the conjecture is false.

See S. Gutner, The complexity of planar graph choosability. Discrete Math. 159 (1996), no. 1-3, 119–130 and

Voigt, M.; Wirth, B. On $3$-colorable non-$4$-choosable planar graphs. J. Graph Theory 24 (1997), no. 3, 233–235.

Thanks for the references. I was not aware of them. Looking forward to reading them.

is there any algorithm exist for list coloring of planer graph?

You have the paper of Vadin Vizing about this problem Choosability?