List homomorphisms of graphs with bounded degrees

DOI10.1016/j.disc.2005.09.030zbMath1111.05035MaRDI QIDQ864125

Jing Huang, Tomás Feder, Pavol Hell

Publication date: 13 February 2007

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

Full work available at URL: https://doi.org/10.1016/j.disc.2005.09.030

zbMATH Keywords

polynomial-time algorithm; extension problem; NP-complete problem; bi-arc graph; edge-asteroid; H-colouring problem

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Bounded Tree-Width and CSP-Related Problems, Hard constraint satisfaction problems have hard gaps at location 1, List homomorphisms of graphs with bounded degrees, Dichotomy for bounded degree \(H\)-colouring, Extension problems with degree bounds, A combinatorial constraint satisfaction problem dichotomy classification conjecture, List homomorphisms to reflexive graphs, Complexity of homomorphisms to direct products of graphs

Cites Work

• Unnamed Item
• 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
• Graph homomorphisms and phase transitions
• The complexity of \(H\)-colouring of bounded degree graphs
• List homomorphisms and circular arc graphs
• On the complexity of the general coloring problem
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Bi‐arc graphs and the complexity of list homomorphisms