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

Read Full Post »

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

Read Full Post »

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 or . Heuristica [...]

Read Full Post »