H-coloring degree-bounded (acyclic) digraphs
DOI10.1016/J.TCS.2014.06.014zbMATH Open1382.68112OpenAlexW2065415255MaRDI QIDQ744083FDOQ744083
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
Recommendations
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the complexity of H-coloring
- Consistency in networks of relations
- The NP-Completeness of Edge-Coloring
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Title not available (Why is that?)
- On the algebraic structure of combinatorial problems
- Colouring, constraint satisfaction, and complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Hard constraint satisfaction problems have hard gaps at location 1
- Duality and Polynomial Testing of Tree Homomorphisms
- The complexity of \(H\)-colouring of bounded degree graphs
- Colouring graphs when the number of colours is nearly the maximum degree
- The Complexity of Colouring by Semicomplete Digraphs
- Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
- List homomorphisms of graphs with bounded degrees
- On the complexity of the general coloring problem
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- Dichotomy for bounded degree \(H\)-colouring
- Universality of \(A\)-mote graphs
- Small \(H\)-coloring problems for bounded degree digraphs
Cited In (7)
- Acyclic Homomorphisms and Circular Colorings of Digraphs
- Surjective H-Colouring over Reflexive Digraphs
- The complexity of \(H\)-colouring of bounded degree graphs
- Digraph coloring and distance to acyclicity
- Dichotomy for bounded degree \(H\)-colouring
- H-absorbence and H-independence in 3-quasi-transitive H-coloured digraphs.
- Small \(H\)-coloring problems for bounded degree digraphs
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)
