Colorings and homomorphisms of degenerate and bounded degree graphs (Q5936036)

A graph \(G\) is said to have an \(H\)-coloring, where \(H\) is another graph, if there is a homomorphism of \(G\) into \(H\). It is known that the \(H\)-coloring problem is polynomial when \(H\) is bipartite and NP-complete otherwise. The famous Brooks' theorem implies that the \(K_3\)-coloring problem is easy for cubic graphs. It is also known that it is easy for \(2\)-degenerate graphs. One main result of the authors is that, for a non-bipartite triangle-free graph \(H\), the \(H\)-coloring problem is NP-complete for the class of \(2\)-degenerate graphs. The \(C_5\)-coloring problem is known to be NP-complete for cubic graphs. Regarding the conjecture that any cubic graph with sufficiently large girth is \(C_5\)-colorable, the authors show that there are cubic graphs of girth \(7\) which are not \(C_5\)-colorable. They further show that it is not true that cubic graphs with sufficiently large girth are \(C_k\)-colorable for \(k\geq 11\). As a proof technique, the authors use an ``indicator construction'' and some modifications of it.