Polynomial graph-colorings (Q1183345)

For directed graphs \(G=(V_ G,E_ G)\) and \(H=(V_ H,E_ H)\) an \(H\)- coloring of \(G\) is a mapping \(f:V_ G\to V_ H\) such that for all edges \((u,v)\in E_ G\) we have \((f(u),f(v))\in E_ H\). The authors introduce a new technique for proving that the \(H\)-coloring problem is polynomially solvable for some fixed digraphs \(H\). Among others, there are semipaths (paths with edges directed in either direction), a fact which was not previously known. The result for semipaths is ``strong'' in the sense that there exists a tree \(T\) (also shown by the authors) for which the \(T\)-coloring problem is NP-complete.