Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418828 | Discrete Applied Mathematics | 2009 | 8 Pages |
Abstract
We have proved in an earlier paper that the complexity of the list homomorphism problem, to a fixed graph HH, does not change when the input graphs are restricted to have bounded degrees (except in the trivial case when the bound is two). By way of contrast, we show in this paper that the extension problem, again to a fixed graph HH, can, in some cases, become easier for graphs with bounded degrees.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Tomas Feder, Pavol Hell, Jing Huang,