Colorings and homomorphisms of degenerate and bounded degree graphs

Abstrakt

We relate homomorphisms of graphs to graph degeneracy and bounded degree property. In the abundance of counterexamples and from the complexity point of view the Brook's theorem and first fit algorithm are the 'only' easy cases.