List Coloring of Planar Graphs

I have been reading some papers on list-coloring of planar graphs. Here's a quick overview of this topic.

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 (4CT) states that "Evey planar graph is 4-colorable". This is tight, since K4 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 states that "Every triangle-tree planar graph is 3-colorable".

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 :

• 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]. 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].

• Conjecture : Every 3-colorable planar graph is 4-choosable.
  

Note : A recent paper [DKT'08], presents a very short proof of Grotzsch's theorem and a linear-time algorithm for 3-coloring such graphs.

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. To appear in SODA 09.
  

Testing triangle-freeness

Given an undirected graph G(V,E), how fast can we detect if G is triangle-free ? Cubic time is obvious. Let A be the adjacency matrix of G. We can detect triangle-freeness of G in the same complexity as multiplying two boolean matrices (AxA) (duh !!). This simple algorithm is the best known !! In other words, following is the open problem :

• Is testing triangle-freeness as difficult as the Boolean multiplication of two |V| x |V | matrices?
  

A recent paper [1] addressess this problem partially. In a related note, the complexity of all pairs shortest paths (APSP) is still unresolved. Is APSP (for undirected graphs) as difficult as the Boolean multiplication of two |V| x |V | matrices?


[1] N. Alon, T. Kaufman, M. Krivelevich, and D. Ron. Testing triangle-freeness in general graphs. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 279–-288, 2006.

Tiling chessboard by L-shaped trominoes

Can you cover all but one square of an n x n chessboard by L-shaped trominoes?

Claim : If n is a power of 2, you can always do it !!

Have fun proving this !!

Lipton Symposium and Trotter Conference

I am eagerly waiting for the following two excellent conferences at GeorgiaTech :

• The Lipton Theory Symposium (Apr 26 - Apr 28 2008) : Celebrating Dick Lipton's 60th birthday. Consists of very diverse and interesting set of talks.
  

• New Directions in Algorithms, Combinatorics and Optimization (May 5 - May 9 2008) : Honoring the 65th Birthday of William T. Trotter. Excellent set of invited speakers and talks.
  

25 Horses Puzzle

There are 25 horses and only five tracks in a race (i.e., you can race 5 horses at a time). There is no stop clock !! Assume that there are no ties.

1: What is the minimum number of races needed to determine the 3 fastest horses in order from fastest to slowest ?
2: ..... to find out the fastest one ?
3: ..... to rank all of them from fastest to slowest ?
4: ..... to find the top k fastest horses ?