Hereditarily hard \(H\)-colouring problems
From MaRDI portal
Publication:1842146
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
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
