Counting list homomorphisms and graphs with bounded degrees
Tomás Feder, Pavol Hell, Jing Huang · 2001
Abstract In a series of papers we have classified the complexity of list homomorphism problems.Here we investigate the effect of restricting the degrees of the input graphs. It turns out that the complexity does not change (except when the degree bound is two). We obtain similarresults on restricting the size of the lists. We contrast these results with facts about some variants of the list homomorphism prob-lem, where restricting the degrees can have an important effect on the complexity.