POLYNOMIAL GRAPH-COLORINGS

For directed graphs G and H, we say that G is H-colorable, if there is a graph homomorphism from G into H; that is, there is a mapping f from the vertex set of G into the vertex set of H such that whenever there is an edge (x,y) in G, then (f(x),f(y)) is an edge in H. We introduce a new technique for proving that the H-coloring problem is polynomial time decidable for some fixed graphs H. Among others, this is the case if H is a semipath (a "path" with edges directed in either direction), which was not previously known. We also show the existence of a tree T, for which the T-coloring problem is NP-complete.