On the complexity of H-coloring

From MaRDI portal

Publication:1100215

Jump to:navigation, search

DOI10.1016/0095-8956(90)90132-JzbMath0639.05023OpenAlexW2077575555WikidataQ56389113 ScholiaQ56389113MaRDI QIDQ1100215

Jaroslav Nešetřil, Pavol Hell

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

zbMATH Keywords

graph coloring NP-completeness graph homomorphism polynomial algorithms H-coloring

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)

Related Items

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 ⋮ 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 ⋮ Unnamed Item ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ Unnamed Item ⋮ Computational complexity relationship between compaction, vertex-compaction, and retraction ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Complexity of Digraph Colourings and Vertex Arboricity ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ 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 ⋮ The complexity of colouring symmetric relational systems ⋮ Tractability in constraint satisfaction problems: a survey ⋮ In praise of homomorphisms ⋮ Good and semi-strong colorings of oriented planar graphs ⋮ Graph homomorphisms with infinite targets ⋮ Homomorphisms to oriented paths ⋮ Coloring problems on bipartite graphs of small diameter ⋮ Oriented incidence colourings of digraphs ⋮ Algorithms to approximately count and sample conforming colorings of graphs ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ Minimum cost homomorphism dichotomy for oriented cycles ⋮ Holant problems for 3-regular graphs with complex edge functions ⋮ The complexity of restricted graph homomorphisms ⋮ Colorings and girth of oriented planar graphs ⋮ On the distance and multidistance graph embeddability problem ⋮ On a new reformulation of Hadwiger's conjecture ⋮ Axiomatisability and hardness for universal Horn classes of hypergraphs ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ Testing list \(H\)-homomorphisms ⋮ List homomorphisms of graphs with bounded degrees ⋮ A complexity dichotomy for signed \(\mathbf{H}\)-colouring ⋮ Mixed hypergraphs and other coloring problems ⋮ Computational complexity of compaction to irreflexive cycles ⋮ Multiplicativity of acyclic digraphs ⋮ Algorithms for partition of some class of graphs under compaction and vertex-compaction ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Circuit satisfiability and constraint satisfaction around Skolem arithmetic ⋮ List homomorphisms to reflexive graphs ⋮ Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ Obtaining online ecological colourings by generalizing first-fit ⋮ Covering regular graphs ⋮ Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions ⋮ A strong Mal'cev condition for locally finite varieties omitting the unary type ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ On complexity of multidistance graph recognition in \(\mathbb{R}^1\) ⋮ Conservative constraint satisfaction re-revisited ⋮ A new line of attack on the dichotomy conjecture ⋮ Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy. ⋮ Enumerating homomorphisms ⋮ Exact algorithms for \(L(2,1)\)-labeling of graphs ⋮ The complexity of the \(T\)-coloring problem for graphs with small degree ⋮ Tension continuous maps -- their structure and applications ⋮ On the homomorphism order of labeled posets ⋮ Acyclic homomorphisms to stars of graph Cartesian products and chordal bipartite graphs ⋮ Holographic algorithms beyond matchgates ⋮ New plain-exponential time classes for graph homomorphism ⋮ Homomorphic preimages of geometric paths ⋮ A note on random homomorphism from arbitrary graphs to \(\mathbb{Z}\) ⋮ Homomorphisms and oriented colorings of equivalence classes of oriented graphs ⋮ \(H\)-colorings of dense hypergraphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Computational complexity of auditing finite attributes in statistical databases ⋮ Polynomial graph-colorings ⋮ A note on restricted \(H\)-colouring ⋮ Minimum cost homomorphisms to semicomplete multipartite digraphs ⋮ On the restricted homomorphism problem ⋮ The monotonicity property of \(M\)-partition problems ⋮ Hedetniemi's conjecture and adjoint functors in thin categories ⋮ The complexity of counting quantifiers on equality languages ⋮ On the complexity of colouring by superdigraphs of bipartite graphs ⋮ The core of a graph ⋮ Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms ⋮ List H-coloring a graph by removing few vertices ⋮ Colorings at minimum cost ⋮ A computational proof of complexity of some restricted counting problems ⋮ The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops ⋮ The restrictive \(H\)-coloring problem ⋮ Recognizing frozen variables in constraint satisfaction problems ⋮ Resource-sharing system scheduling and circular chromatic number ⋮ The complexity of colouring by locally semicomplete digraphs ⋮ The complexity of locally injective homomorphisms ⋮ A new tractable class of constraint satisfaction problems ⋮ Approximability and inapproximability of the minimum certificate dispersal problem ⋮ The complexity of homomorphisms and renamings for minimal unsatisfiable formulas ⋮ Computing vertex-surjective homomorphisms to partially reflexive trees ⋮ Finding vertex-surjective graph homomorphisms ⋮ Hom complexes and homotopy theory in the category of graphs ⋮ Dichotomy for bounded degree \(H\)-colouring ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs ⋮ Partially ordered connectives and monadic monotone strict NP ⋮ Extension problems with degree bounds ⋮ Finite dualities and map-critical graphs on a fixed surface ⋮ Generalized partitions of graphs ⋮ Homomorphisms of hexagonal graphs to odd cycles ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Edge-switching homomorphisms of edge-coloured graphs ⋮ On the complexity of \(H\)-colouring planar graphs ⋮ On universal graphs for planar oriented graphs of a given girth ⋮ Conjunctive-query containment and constraint satisfaction ⋮ Homomorphisms to oriented cycles ⋮ Complexity of homomorphisms to direct products of graphs ⋮ Counting \(H-\)colorings of partial \(k-\)trees ⋮ Distance constraint satisfaction problems ⋮ A dichotomy for real weighted Holant problems ⋮ An efficient algorithm for a class of constraint satisfaction problems ⋮ \(H\)-coloring dichotomy revisited ⋮ \(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 ⋮ Complexity of tree homomorphisms ⋮ Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets ⋮ Correspondence homomorphisms to reflexive graphs ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ The dynamic complexity of acyclic hypergraph homomorphisms ⋮ Complexity of correspondence \(H\)-colourings ⋮ The complexity of approximating bounded-degree Boolean \(\#\)CSP ⋮ From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems ⋮ Graph homomorphisms via vector colorings ⋮ Host-graph-sensitive RETE nets for incremental graph pattern matching with nested graph conditions ⋮ On digraph coloring problems and treewidth duality ⋮ Locally constrained graph homomorphisms and equitable partitions ⋮ Generalised dualities and maximal finite antichains in the homomorphism order of relational structures ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ Low-level dichotomy for quantified constraint satisfaction problems ⋮ Matrix partitions of perfect graphs ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ Exact algorithm for graph homomorphism and locally injective graph homomorphism ⋮ Complexity of Locally Injective Homomorphism to the Theta Graphs ⋮ Unnamed Item ⋮ On rainbow-free colourings of uniform hypergraphs ⋮ On Maltsev Digraphs ⋮ Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees ⋮ On the CSP Dichotomy Conjecture ⋮ Locally Injective Homomorphism to the Simple Weight Graphs ⋮ On realizations of point determining graphs, and obstructions to full homomorphisms ⋮ On the computational complexity of partial covers of theta graphs ⋮ Retractions onto series-parallel posets ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ On Maltsev digraphs ⋮ Surjective \(H\)-colouring: new hardness results ⋮ The complexity of tropical graph homomorphisms ⋮ Level of repair analysis and minimum cost homomorphisms of graphs ⋮ Minimum cost and list homomorphisms to semicomplete digraphs ⋮ The ferry cover problem ⋮ Optimal data reduction for graph coloring using low-degree polynomials ⋮ Dichotomy for tree-structured trigraph list homomorphism problems ⋮ On systematic scan for sampling H-colorings of the path ⋮ Building blocks for the variety of absolute retracts ⋮ THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA ⋮ Dichotomy for Holant\(^\ast\) problems on the Boolean domain ⋮ Graph partitions with prescribed patterns ⋮ Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties. ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard ⋮ The local loop lemma ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ Minimum Cost Homomorphisms with Constrained Costs ⋮ New Plain-Exponential Time Classes for Graph Homomorphism ⋮ Two-element structures modulo primitive positive constructability ⋮ CSP dichotomy for special triads ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Cryptanalysis and improvements on some graph-based authentication schemes ⋮ On the Complexity of Planar Covering of Small Graphs ⋮ Density of \(C_{-4}\)-critical signed graphs ⋮ Adjusted Interval Digraphs ⋮ The number of clones determined by disjunctions of unary relations ⋮ \(H\)-colouring \(P_t\)-free graphs in subexponential time ⋮ A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights ⋮ The recognition of bound quivers using edge-coloured homomorphisms ⋮ Hereditarily hard \(H\)-colouring problems ⋮ Extended Gallai's Theorem ⋮ CSP DICHOTOMY FOR SPECIAL POLYADS ⋮ On inverse powers of graphs and topological implications of Hedetniemi's conjecture ⋮ A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results ⋮ Duality theorems for finite structures (characterising gaps and good characterisations) ⋮ Density via duality. ⋮ The complexity of partition functions ⋮ Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}) ⋮ Subdivision of the hierarchy of H-colorable graph classes by circulant graphs ⋮ Between Colorings and Layouts - Minimum Morphism Cost Problems ⋮ Matrix Partitions with Finitely Many Obstructions ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree ⋮ List homomorphism problems for signed trees ⋮ A quasi-Mal'cev condition with unexpected application. ⋮ Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1100215&oldid=13137187"