The Good Will Hunting Problem

Here is a problem from the movie Good Will Hunting, shown in the screenshot below.



For the the graph G(V,E) shown above, find the following :

• The adjacency matrix A :

• The matrix giving the number of 3 step walks in G : [A^k]_ij is the number of paths of length k from i to j. So, the answer is A³.

• The generating function for walks from point i to j : The generating function is as follows. Here are more examples of generating functions.
  

• The generating function for walks from points 1 to 3 : Simplify the above formula using cramer's rule for i=1 and j=3.

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.

Graceful Trees !!

I posted my favorite open problem (is every tree graceful ?) on the open problem garden. There are many more interesting open problems on this site.

Graceful Tree Conjecture

Label the vertices of a simple undirected graph G(V,E) (where V = n and E = m) with integers from 0 to m. Now label each edge with absolute difference of the labels of its incident vertices. The labeling is said to be graceful if the edges are labelled 1 through m inclusive (with no number repeated).

A graph is called graceful if it has atleast one such labeling. This labeling was originally introduced in 1967 by Rosa. The name graceful labeling was coined later by Golomb.

Gracefully labeled graphs serve as models in a wide range of applications including coding theory and communication network addressing.

The graceful labeling problem is to determine which graphs are graceful. It is conjectured (by Kotzig, Ringel and Rosa) that all trees are graceful.

Despite numerous (more than 200) publications on graceful labeling for over three decades, only a very restricted classes of trees have been shown to be graceful. These restriced classes include paths, stars, complete bi-partite graphs, prism graphs, wheel graphs, caterpillar graphs, olive trees, and symmetrical trees.