H-coloring degree-bounded (acyclic) digraphs

DOI10.1016/J.TCS.2014.06.014zbMATH Open1382.68112OpenAlexW2065415255MaRDI QIDQ744083FDOQ744083

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

homomorphismcoloringacyclic digraphdegree-bounded digraph

Mathematics Subject Classification ID

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?)
• Title not available (Why is that?)
• 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
• On the algebraic structure of combinatorial problems
• Colouring, constraint satisfaction, and complexity
• 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 (4)

• Surjective H-Colouring over Reflexive Digraphs
• The complexity of \(H\)-colouring of bounded degree graphs
• Dichotomy for bounded degree \(H\)-colouring
• H-absorbence and H-independence in 3-quasi-transitive H-coloured 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)