Graceful Tree Conjecture

Graceful Tree Conjecture (GTC) is one of my favorite open problems. I posted it on Open Problem Garden couple of years back. I enjoy reading papers related to graceful labeling and try to keep as up-to-date as possible with the progress towards GTC. Here is a brief introduction to GTC.

Graceful Labeling : 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 labeled 1 through m inclusive (with no number repeated).

A graph is called graceful if it has at least one such labeling. This labeling was originally introduced in 1967 by Rosa [Rosa’67]. The name graceful labeling was coined later by Golomb. It is easy to see that stars and paths are graceful. Some known graceful graphs are paths, stars, complete bipartite graphs, prism graphs, wheel graphs, caterpillar graphs, olive trees, and symmetrical trees, gear graphs, rectangular grids.

Gracefully labeled graphs have applications in coding theory and communication network addressing. Look at this paper [Basak’04] for an application in MPLS Multicasting. The following conjecture is due to Kotzig, Ringel and Rosa.

Graceful Tree Conjecture (GTC) : All trees are graceful.

Ringel’s Conjecture : If T is a fixed tree with m edges, then complete graph on 2m+1 vertices decomposes into 2m+1 copies of T.

Exercise : The existence of a graceful labeling of a given graph G with n edges is a sufficient condition for the existence of a cyclic decomposition of a complete graph of order 2n+1 into subgraphs isomorphic to G. In particular, GTC implies Ringel’s conjecture.

A caterpillar graph is a tree such that if all leaves and their incident edges are removed, the remainder of the graph forms a path. Here’s a cute exercise. There is an elegant inductive proof.

Exercise : Prove that all caterpillar graphs are graceful.

Open Problems :

  • Graceful Tree Conjecture (GTC) is still open. There are couple of papers on arxiv claiming to have settled GTC. I went through the proofs and found some mistakes.
  • As an intermediate problem, prove that all lobster graphs are graceful. This is also an open problem. Some special cases of lobsters (eg : lobsters with perfect matching) are proved graceful [Morgan’02].
  • Complexity of graceful labeling is open. A related problem called harmonious labeling was shown to be NP-complete.
  • Improve approximate factors of relaxed graceful labeling [Bussel’02].

References :

  • [Rosa’67] Alex Rosa, On certain valuations of the vertices of a graph. Theory of Graphs, (1967) 349–355
  • [Bussel’02] Frank Van Bussel: Relaxed Graceful Labellings of Trees. Electr. J. Comb. 9(1): (2002)
  • [Morgan’02] David Morgan: All Lobsters with Perfect Matchings are Graceful. Electronic Notes in Discrete Mathematics 11: 503-508 (2002)
  • [Basak’04] Ayhan Basak, MPLS Multicasting Using Caterpillars and a Graceful Labelling Scheme, Eighth International Conference on Information Visualisation (IV’04), pp.382-387, 2004

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

Impagliazzo’s Worlds

I am back in Atlanta after attending Valiant’s birthday celebrations, STOC 2009 and Impagliazzo’s Worlds workshop. Another upcoming workshop at Center for Computational Intractability is “Barriers in Computational Complexity” workshop from August 25-29, 2009. Today’s post is a brief introduction to the five Impagliazzo’s Worlds [Impagliazzo’95].

Algorithmica is the world in which P=NP or NP \subseteq BPP.

Heuristica is the world where NP problems are intractable in the worst case but tractable on average.

Pessiland is the world in which there are hard average-case problems, but no one-way functions. As the name suggests this is the worst possible world.

Minicrypt is the world in which one-way functions exist, but public-key cryptography is impossible.

Cryptomania is the world in which public-key cryptography is possible.

Open Problems : An obvious open problem is which world do we live in ? Does Pessiland exist ?

References :

  • [Impagliazzo’95] Russell Impagliazzo : A Personal View of Average-Case Complexity. Structure in Complexity Theory Conference 1995: 134-147 [ps]