×

Extension problems with degree bounds. (English) Zbl 1177.05037

Summary: We have proved in an earlier paper that the complexity of the list homomorphism problem, to a fixed graph \(H\), 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 \(H\), can, in some cases, become easier for graphs with bounded degrees.

MSC:

05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albertson, M. O.; Moore, E. H., Extending graph colourings, J. Combin. Theory B, 77, 83-95 (1999) · Zbl 1024.05027
[2] Bollobás, B., Extremal Graph Theory (1978), Academic Press · Zbl 0419.05031
[3] Brooks, R. L., On coloring of nodes of a network, Proc. Cambridge Phil. Soc., 37, 194-197 (1941) · Zbl 0027.26403
[4] Díaz, J.; Serna, M.; Thilikos, D. M., Recent results on parametrized \(H\)-colourings, (Nešetřil, J.; Winkler, P., Graphs, Morphisms and Statistical Physics. Graphs, Morphisms and Statistical Physics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 63 (2004)), 105-112
[5] Feder, T.; Hell, P., List homomorphisms to reflexive graphs, J. Combin. Theory B, 72, 236-250 (1998) · Zbl 0904.05078
[6] Feder, T.; Hell, P.; Huang, J., List homomorphisms and circular arc graphs, Combinatorica, 19, 487-505 (1999) · Zbl 0985.05048
[7] Feder, T.; Hell, P.; Huang, J., Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory, 42, 61-80 (2003) · Zbl 1057.05033
[8] Feder, T.; Hell, P.; Huang, J., List homomorphisms of graphs with bounded degrees, Discrete Math., 307, 386-392 (2007) · Zbl 1111.05035
[9] Feder, T.; Hell, P.; Huang, J., Brooks-type theorems for pair-list colourings and list homomorphisms, SIAM J. Discrete Math., 22, 1-14 (2008) · Zbl 1156.05019
[10] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory, SIAM J. Comput., 28, 236-250 (1998) · Zbl 0914.68075
[11] Galluccio, A.; Hell, P.; Nešetřil, J., The complexity of \(H\)-colouring of bounded degree graphs, Discrete Math., 222, 101-109 (2000) · Zbl 0956.05036
[12] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0411.68039
[13] Hell, P.; Nešetřil, J., On the complexity of \(H\)-colouring, J. Combin. Theory B, 48, 92-110 (1990) · Zbl 0639.05023
[14] Hell, P.; Nešetřil, J., Counting list homomorphisms of graphs with bounded degrees, (Nešetřil, J.; Winkler, P., Graphs, Morphisms and Statistical Physics. Graphs, Morphisms and Statistical Physics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 63 (2004)), 105-112 · Zbl 1059.05049
[15] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press · Zbl 1062.05139
[16] Kratochvíl, J.; Sebő, A., Coloring precolored perfect graphs, J. Graph Theory, 25, 207-215 (1997) · Zbl 0876.05035
[17] Kratochvíl, J.; Tuza, Z., Algorithmic complexity of list colorings, Discrete Appl. Math., 50, 297-302 (1994) · Zbl 0807.68055
[18] M. Siggers, On the bounded degree restriction of constraint satisfaction problems, Discrete Appl. Math. (in press); M. Siggers, On the bounded degree restriction of constraint satisfaction problems, Discrete Appl. Math. (in press)
[19] Telle, J. A.; Proskurowski, A., Algorithms for vertex partitioning problems on partial \(k\)-trees, SIAM J. Discrete Math., 10, 529-550 (1997) · Zbl 0885.68118
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.