A note on restricted \(H\)-colouring (Q1183461): Difference between revisions

Let \(H\) be a graph whose vertices are called colors. An \(H\)-coloring of a graph \(G\) is a function \(f:V(G)\to V(H)\) such that \((f(u),f(v))\) is an edge of \(H\) whenever \((u,v)\) is an edge in \(G\). The authors consider the complexity of the following problem: ``Given a \(k\)-chromatic graph \(G\) and a \(k\)-coloring of its vertices; does there exist an \(H\)-coloring of \(G\)?'' They prove that if \(H\) is loopless and the clique number \(\omega(H)\) is less than \(k\leq\chi(H)\), then the problem is NP-hard. Otherwise it is polynomially solvable.