Colorings and homomorphisms of degenerate and bounded degree graphs

Abstract

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.