H-coloring degree-bounded (acyclic) digraphs

DOI10.1016/J.TCS.2014.06.014MaRDI QIDQ744083zbMATH OpenOpenAlexFDO

Authors Pavol Hell, Aurosish Mishra

Publication date 6 October 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.06.014

zbMATH Keywords

acyclic digraphcoloringdegree-bounded digraphhomomorphism

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Small \(H\)-coloring problems for bounded degree digraphs
• Dichotomy for bounded degree \(H\)-colouring
• The complexity of \(H\)-colouring of bounded degree graphs
• Acyclic Homomorphisms and Circular Colorings of Digraphs
• scientific article; zbMATH DE number 866665

Cites work

• A combinatorial constraint satisfaction problem dichotomy classification conjecture
• Colouring graphs when the number of colours is nearly the maximum degree
• Colouring, constraint satisfaction, and complexity
• Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
• Consistency in networks of relations
• Dichotomy for bounded degree \(H\)-colouring
• Duality and Polynomial Testing of Tree Homomorphisms
• Hard constraint satisfaction problems have hard gaps at location 1
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2151253 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 5485593 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• List homomorphisms of graphs with bounded degrees
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• On the complexity of the general coloring problem
• Small \(H\)-coloring problems for bounded degree digraphs
• The complexity of \(H\)-colouring of bounded degree graphs
• The Complexity of Colouring by Semicomplete Digraphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The NP-Completeness of Edge-Coloring
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Universality of \(A\)-mote graphs

Cited in

(7)

• Dichotomy for bounded degree \(H\)-colouring
• The complexity of \(H\)-colouring of bounded degree graphs
• Acyclic Homomorphisms and Circular Colorings of Digraphs
• Small \(H\)-coloring problems for bounded degree digraphs
• H-absorbence and H-independence in 3-quasi-transitive H-coloured digraphs.
• Surjective H-Colouring over Reflexive Digraphs
• Digraph coloring and distance to acyclicity

This page was built for publication: \(H\)-coloring degree-bounded (acyclic) digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744083)