On the complexity of H-coloring
From MaRDI portal
Publication:1100215
DOI10.1016/0095-8956(90)90132-JzbMath0639.05023OpenAlexW2077575555WikidataQ56389113 ScholiaQ56389113MaRDI QIDQ1100215
Publication date: 1990
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(90)90132-j
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items (only showing first 100 items - show all)
Quantified Constraint Satisfaction Problem on Semicomplete Digraphs ⋮ CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Small Promise CSPs that reduce to large CSPs ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Chromatic number of a line with geometric progressions of forbidden distances and the complexity of recognizing distance graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graph covers: where topology meets computer science, and simple means difficult ⋮ Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ The smallest hard trees ⋮ Semidefinite programming and its applications to NP problems ⋮ List homomorphisms to separable signed graphs ⋮ Min orderings and list homomorphism dichotomies for signed and unsigned graphs ⋮ \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's ⋮ List covering of regular multigraphs with semi-edges ⋮ First-Order Model Checking Problems Parameterized by the Model ⋮ Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs ⋮ The complexity of the matroid homomorphism problem ⋮ Unnamed Item ⋮ Minimum Cost Homomorphism Dichotomy for Oriented Cycles ⋮ Computing a partition function of a generalized pattern-based energy over a semiring ⋮ Complexity of graph covering problems ⋮ Tight Lower Bounds for the Complexity of Multicoloring ⋮ Unnamed Item ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Circular chromatic number of induced subgraphs of Kneser graphs ⋮ Unnamed Item ⋮ Quantified Constraints in Twenty Seventeen ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Path homomorphisms ⋮ On generating all solutions of generalized satisfiability problems ⋮ Unnamed Item ⋮ Fanout limitations on constraint systems ⋮ Colouring Random Empire Trees ⋮ Host-Graph-Sensitive RETE Nets for Incremental Graph Pattern Matching ⋮ Unnamed Item ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ Unnamed Item ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The complexity of \((P_k, P_\ell ) \)-arrowing ⋮ Reasoning on property graphs with graph generating dependencies ⋮ Generalisations of matrix partitions: complexity and obstructions ⋮ On the Complexity of Digraph Colourings and Vertex Arboricity ⋮ Min orderings and list homomorphism dichotomies for graphs and signed graphs ⋮ Moduli spaces of geometric graphs ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ Circular coloring of signed bipartite planar graphs ⋮ Loop conditions for strongly connected digraphs ⋮ Homomorphism Reconfiguration via Homotopy ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ The Complexity of Counting Surjective Homomorphisms and Compactions ⋮ Constraint Satisfaction Problems for Reducts of Homogeneous Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon ⋮ Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2 ⋮ Recent Results on the Algebraic Approach to the CSP ⋮ Dualities for Constraint Satisfaction Problems ⋮ A Logical Approach to Constraint Satisfaction ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ Introduction to the Maximum Solution Problem ⋮ Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs ⋮ Almost All Friendly Matrices Have Many Obstructions ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2 ⋮ Homomorphisms of Signed Graphs ⋮ \(H\)-chromatic symmetric functions ⋮ The complexity of Boolean matrix root computation ⋮ Dichotomies for classes of homomorphism problems involving unary functions ⋮ Complexity issues on bounded restrictive \(H\)-coloring ⋮ Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ The complexity of minimal satisfiability problems ⋮ Constraint Satisfaction Problems over the Integers with Successor ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ A Galois Connection for Valued Constraint Languages of Infinite Size ⋮ Approximately Counting H-Colourings is $$\#\mathrm {BIS}$$-Hard ⋮ Counting Homomorphisms to Square-Free Graphs, Modulo 2 ⋮ Algebraic Properties of Valued Constraint Satisfaction Problem ⋮ The complexity of signed graph and edge-coloured graph homomorphisms ⋮ On the Complexity of the Model Checking Problem ⋮ Unnamed Item ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic ⋮ The Complexity of Counting Quantifiers on Equality Languages ⋮ Star chromatic numbers of hypergraphs and partial Steiner triple systems ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Homomorphically full graphs ⋮ Analogues of cliques for \((m,n)\)-colored mixed graphs ⋮ The complexity of generalized graph colorings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On multiplicative graphs and the product conjecture
- Colorings and interpretations: a connection between graphs and grammar forms
- On minimal graphs
- On classes of relations and graphs determined by subobjects and factorobjects
- NP-completeness of a family of graph-colouring problems
- Symmetric relations (undirected graphs) with given semigroups
- Absolute planar retracts and the four colour conjecture
- Some new good characterizations for directed graphs
- Improving the performance guarantee for approximate graph coloring
- On unavoidable digraphs in orientations of graphs
- Cohomomorphisms of graphs and hypergraphs
- A graph coloring algorithm for large scheduling problems
- On the complexity of the general coloring problem
- The Complexity of Near-Optimal Graph Coloring
- An application of graph coloring to printed circuit testing
- The NP-completeness column: An ongoing guide
This page was built for publication: On the complexity of H-coloring
