\(H\)-coloring degree-bounded (acyclic) digraphs
From MaRDI portal
Publication:744083
DOI10.1016/j.tcs.2014.06.014zbMath1382.68112OpenAlexW2065415255MaRDI QIDQ744083
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
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Colouring, constraint satisfaction, and complexity
- Hard constraint satisfaction problems have hard gaps at location 1
- List homomorphisms of graphs with bounded degrees
- Dichotomy for bounded degree \(H\)-colouring
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- On the complexity of H-coloring
- Universality of \(A\)-mote graphs
- Consistency in networks of relations
- On the algebraic structure of combinatorial problems
- The complexity of \(H\)-colouring of bounded degree graphs
- Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
- The Complexity of Colouring by Semicomplete Digraphs
- The NP-Completeness of Edge-Coloring
- On the complexity of the general coloring problem
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Duality and Polynomial Testing of Tree Homomorphisms
- Small H-Coloring Problems for Bounded Degree Digraphs
- Colouring graphs when the number of colours is nearly the maximum degree
This page was built for publication: \(H\)-coloring degree-bounded (acyclic) digraphs
