A digraph whose longest directed path<=k is k-colorable

To prove this theorem, we have the following steps: (first I will assume the graph G is weakly connected)

(i) Find a maximal subgraph H of G which contains no directed cycles.
(ii) Prove that this subgraph H can be k-colored such that if v->u, then the color number c(v) is strictly less than c(u).
(iii) If we add any directed edges into H, it must result a cycle. Use (ii) to show the two end vertices of this edge has different colors.

The main difficulty lies in step (ii). Let’s also divide it into several small steps: (remember that now our graph contains no directed cycles.)

(ii.1) Find a longest directed path (its length is k), choose its starting vertex v. Then for every vertex u which can be reached from v, give it the color c(u)= maximal length of directed path from v to u.
(ii.2) Prove that for every u1, u2 s.t. c(u1)=c(u2), there is no edge between them. Therefore, so far our coloring is proper.
(ii.3) From the remaining vertices, find a vertex w such that it maximize the following thing:
the maximal length of paths from w which doesn’t touch any colored vertices except the last one – the color number of the last vertex.
Then for any uncolored x, let c(x)=maximal length of paths from w to x which doesn’t touch any colored vertices. Like in step (ii.1) and (ii.2), we can also prove that so far the coloring is proper.
(ii.4) Continue this process, since G is weakly connected. We will finally get a proper coloring of all the vertices.

April 25, 2008. Uncategorized. Leave a comment.