We are interested here in homomorphisms of undirected graphs and relate them to graph degeneracy and bounded degree property. Our main result reads that both in the abundance of counterexamples and from the complexity point of view the Brooks's theorem and first fit algorithm are the 'only' easy cases.
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics