List Coloring of Planar Graphs

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 O(n{\log}n) 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
About these ads

5 thoughts on “List Coloring of Planar Graphs

  1. 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.

  2. 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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s