Extension problems with degree bounds

DOI10.1016/j.dam.2008.04.006zbMath1177.05037OpenAlexW2015196367MaRDI QIDQ1028134

Jing Huang, Pavol Hell, Tomás Feder

Publication date: 30 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.04.006

zbMATH Keywords

NP-completenesspolynomial algorithmdichotomybounded degree graphlist homomorphismextension problems for cyclespre-colouring extension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Graph partitions with prescribed patterns

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• List homomorphisms of graphs with bounded degrees
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Algorithmic complexity of list colorings
• Extending graph colorings
• The complexity of \(H\)-colouring of bounded degree graphs
• List homomorphisms and circular arc graphs
• Brooks-Type Theorems for Pair-List Colorings and List Homomorphisms
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Bi‐arc graphs and the complexity of list homomorphisms