Colouring, constraint satisfaction, and complexity
type: Item
instance of: scholarly article
title: Colouring, constraint satisfaction, and complexity
zbMATH Open document ID: 1302.68251
author: Pavol Hell
author: J. Nešetřil
published in: Computer Science Review
publication date: 2014-10-07T00:00:00Z
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68-02
zbMATH DE Number: 6352099
MaRDI profile type: Publication
full work available at URL: j.cosrev.2008.10.003
OpenAlex ID: W2199961663
cites work: Q3184605
cites work: Q3424887
cites work: Graph products, Fourier analysis and spectral techniques
cites work: Proof verification and the hardness of approximation problems
cites work: On digraph coloring problems and treewidth duality
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Absolute retracts of bipartite graphs
cites work: Absolute reflexive retracts and absolute bipartite retracts
cites work: Efficient characterizations of \(n\)-chromatic absolute retracts
cites work: The effect of two cycles on the complexity of colourings by directed graphs
cites work: The Complexity of Colouring by Semicomplete Digraphs
cites work: On the complexity of colouring by superdigraphs of bipartite graphs
cites work: Hereditarily hard \(H\)-colouring problems
cites work: The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
cites work: Precoloring extension. I: Interval graphs
cites work: Varieties with few subalgebras of powers
cites work: Q3424888
cites work: Near-Unanimity Functions and Varieties of Reflexive Graphs
cites work: \(H\)-coloring dichotomy revisited
cites work: A Simple Algorithm for Mal'tsev Constraints
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: Dualities for Constraint Satisfaction Problems
cites work: Q5501285
cites work: Q4677979
cites work: The strong perfect graph theorem
cites work: Star-cutsets and perfect graphs
cites work: Characterising tractable constraints
cites work: Q5715675
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: A new tractable class of constraint satisfaction problems
cites work: Generalized Majority-Minority Operations are Tractable
cites work: Mathematical Foundations of Computer Science 2003
cites work: First-order Definable Retraction Problems for Posets and Reflexive Graphs
cites work: Retractions onto series-parallel posets
cites work: A combinatorial algorithm for MAX CSP
cites work: The PCP theorem by gap amplification
cites work: Independent sets in graph powers are almost contained in juntas
cites work: Linear-time algorithms for testing the satisfiability of propositional horn formulae
cites work: Q3113761
cites work: Q4058132
cites work: Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
cites work: A Dichotomy Theorem on Fixed Points of Several Nonexpansive Mappings
cites work: Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection
cites work: List homomorphisms to reflexive graphs
cites work: Full Constraint Satisfaction Problems
cites work: Matrix partitions of perfect graphs
cites work: On realizations of point determining graphs, and obstructions to full homomorphisms
cites work: List homomorphisms and circular arc graphs
cites work: Bi‐arc graphs and the complexity of list homomorphisms
cites work: List homomorphisms of graphs with bounded degrees
cites work: List Partitions
cites work: List matrix partitions of chordal graphs
cites work: Two algorithms for general list matrix partitions
cites work: Acyclic Homomorphisms and Circular Colorings of Digraphs
cites work: Digraph matrix partitions and trigraph homomorphisms
cites work: Q3424776
cites work: Dichotomies for classes of homomorphism problems involving unary functions
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Locally constrained graph homomorphisms -- structure, complexity, and applications
cites work: Q4521527
cites work: Q4193514
cites work: Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
cites work: Reflection positivity, rank connectivity, and homomorphism of graphs
cites work: Q5545303

Colouring, constraint satisfaction, and complexity (cites work)
cites work: The complexity of \(H\)-colouring of bounded degree graphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q4198056

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Closed systems of functions and predicates

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q3328583

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Applications of product colouring

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Minimum Cost Homomorphisms to Reflexive Digraphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q3565872

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: A dichotomy for minimum cost graph homomorphisms

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Minimum cost and list homomorphisms to semicomplete digraphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q3615793

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Polynomial graph-colorings

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q3903002

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Zur algebraischen Begründung der Graphentheorie. I

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Absolute planar retracts and the four colour conjecture

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q4049082

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q3424890

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q4432211

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Partitioning chordal graphs into independent sets and cliques

Colouring, constraint satisfaction, and complexity (cites work)
cites work: The core of a graph

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q4878664

Colouring, constraint satisfaction, and complexity (cites work)
cites work: On the complexity of H-coloring

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q4660723

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q4828516

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Complexity of tree homomorphisms

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Duality and Polynomial Testing of Tree Homomorphisms

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Absolute Retracts and Varieties of Reflexive Graphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Expander graphs and their applications

Colouring, constraint satisfaction, and complexity (cites work)
cites work: On sentences which are true of direct unions of algebras

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q4838466

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Precoloring Extension III: Classes of Perfect Graphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Tractability and Learnability Arising from Algebras with Few Subpowers

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q3730636

Colouring, constraint satisfaction, and complexity (cites work)
cites work: On the algebraic structure of combinatorial problems

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Closure properties of constraints

Colouring, constraint satisfaction, and complexity (cites work)
cites work: The NP-completeness column: An ongoing guide

Colouring, constraint satisfaction, and complexity (cites work)
cites work: A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.

Colouring, constraint satisfaction, and complexity (cites work)
cites work: The Ramsey number R(3, t) has order of magnitude t2/log t

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Conjunctive-query containment and constraint satisfaction

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Colorings and homomorphisms of degenerate and bounded degree graphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction

Colouring, constraint satisfaction, and complexity (cites work)
cites work: A new line of attack on the dichotomy conjecture

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Forbidden lifts (NP and CSP for combinatorialists)

Colouring, constraint satisfaction, and complexity (cites work)
cites work: On the Structure of Polynomial Time Reducibility

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q5471351

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Projectivity and independent sets in powers of graphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: A Characterisation of First-Order Constraint Satisfaction Problems

Colouring, constraint satisfaction, and complexity (cites work)
cites work: A polynomial-time algorithm for near-unanimity graphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Finite posets and topological spaces in locally finite varieties

Colouring, constraint satisfaction, and complexity (cites work)
cites work: The Complexity of the Extendibility Problem for Finite Posets

Colouring, constraint satisfaction, and complexity (cites work)
cites work: A graph coloring algorithm for large scale scheduling problems

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Note on projective graphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q3424784

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q4094884

Colouring, constraint satisfaction, and complexity (cites work)
cites work: On colorings of graphs without short cycles

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Networks of constraints: Fundamental properties and applications to picture processing

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Aspects of structural combinatorics. (Graph homomorphisms and their use)

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q4871773

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Many Facets of Dualities

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Cuts and bounds

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Folding

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Tree-depth, subgraph coloring and homomorphism bounds

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Linear time low tree-width partitions and algorithmic consequences

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Structural Properties of Sparse Graphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Grad and classes with bounded expansion. I: Decompositions

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Grad and classes with bounded expansion. II: Algorithmic aspects

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities

Colouring, constraint satisfaction, and complexity (cites work)
cites work: On classes of relations and graphs determined by subobjects and factorobjects

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Chromatically optimal rigid graphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete

Colouring, constraint satisfaction, and complexity (cites work)
cites work: A dualistic approach to bounding the chromatic number of a graph

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Duality theorems for finite structures (characterising gaps and good characterisations)

Colouring, constraint satisfaction, and complexity (cites work)
cites work: On sparse graphs with given colorings and homomorphisms.

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Products of absolute retracts

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q4332422

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Q3208855

Colouring, constraint satisfaction, and complexity (cites work)
cites work: A retraction problem in graph theory

Colouring, constraint satisfaction, and complexity (cites work)
cites work: On Dinur’s proof of the PCP theorem

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Nombre chromatique et plus longs chemins d'un graphe

Colouring, constraint satisfaction, and complexity (cites work)
cites work: A graph formulation of a school scheduling algorithm

Colouring, constraint satisfaction, and complexity (cites work)
cites work: The complexity of satisfiability problems

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Computational Complexity of Compaction to Reflexive Cycles

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Interval digraphs: An analogue of interval graphs

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Decomposition by clique separators

Colouring, constraint satisfaction, and complexity (cites work)
cites work: Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane

Colouring, constraint satisfaction, and complexity (Wikidata QID)
Wikidata QID: Q56389140

Colouring, constraint satisfaction, and complexity (DOI)
DOI: 10.1016/J.COSREV.2008.10.003