Graph coloring in linear time (Q921012)

We provide fast algorithms for finding proper vertex colorings of a graph with a small number of colors, when a suitable orientation is given on the edges. Moreover, generalizing Minty's and Gallai and Roy's classic results on oriented paths and cycles vs. chromatic number, we prove new sufficient conditions insuring that a graph is k-colorable. The main idea in the proofs is to apply directed and weighted variants of depth-first- search.