Hereditarily hard \(H\)-colouring problems

DOI10.1016/0012-365X(94)00189-PzbMath0816.68090OpenAlexW2052903450MaRDI QIDQ1842146

Gary MacGillivray, Pavol Hell, Jörgen Bang-Jensen

Publication date: 19 July 1995

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

Full work available at URL: https://doi.org/10.1016/0012-365x(94)00189-p

zbMATH Keywords

digraphH-colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items

Homomorphisms to oriented paths, The complexity of restricted graph homomorphisms, Towards a dichotomy theorem for the counting constraint satisfaction problem, Complexity of tree homomorphisms, The Complexity of Approximately Counting Tree Homomorphisms, The effect of two cycles on the complexity of colourings by directed graphs, Colouring, constraint satisfaction, and complexity, On the restricted homomorphism problem, On the complexity of colouring by superdigraphs of bipartite graphs, The complexity of tropical graph homomorphisms, Graph partitions with prescribed patterns

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of colouring by superdigraphs of bipartite graphs
• The effect of two cycles on the complexity of colourings by directed graphs
• On the complexity of H-coloring
• On multiplicative graphs and the product conjecture
• The directed subgraph homeomorphism problem
• Colorings and interpretations: a connection between graphs and grammar forms
• On minimal graphs
• Color-families are dense
• Polynomial graph-colorings
• On classes of relations and graphs determined by subobjects and factorobjects
• Graph homomorphisms with infinite targets
• Homomorphisms to oriented paths
• Contractibility and NP-completeness
• The Complexity of Colouring by Semicomplete Digraphs
• On the complexity of the general coloring problem
• On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs
• The NP-completeness column: An ongoing guide