Colouring, constraint satisfaction, and complexity
From MaRDI portal
(Redirected from Publication:458466)
Recommendations
Cites work
- scientific article; zbMATH DE number 3650785 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 5531978 (Why is no real title available?)
- scientific article; zbMATH DE number 3962727 (Why is no real title available?)
- scientific article; zbMATH DE number 3711961 (Why is no real title available?)
- scientific article; zbMATH DE number 3463659 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3515489 (Why is no real title available?)
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 978246 (Why is no real title available?)
- scientific article; zbMATH DE number 1996252 (Why is no real title available?)
- scientific article; zbMATH DE number 1545651 (Why is no real title available?)
- scientific article; zbMATH DE number 2151253 (Why is no real title available?)
- scientific article; zbMATH DE number 2170482 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- scientific article; zbMATH DE number 772760 (Why is no real title available?)
- scientific article; zbMATH DE number 863494 (Why is no real title available?)
- scientific article; zbMATH DE number 878894 (Why is no real title available?)
- scientific article; zbMATH DE number 5030273 (Why is no real title available?)
- scientific article; zbMATH DE number 3257176 (Why is no real title available?)
- scientific article; zbMATH DE number 2243365 (Why is no real title available?)
- A Characterisation of First-Order Constraint Satisfaction Problems
- A Dichotomy Theorem on Fixed Points of Several Nonexpansive Mappings
- A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
- A Simple Algorithm for Mal'tsev Constraints
- A combinatorial algorithm for MAX CSP
- A dichotomy for minimum cost graph homomorphisms
- A dualistic approach to bounding the chromatic number of a graph
- A graph coloring algorithm for large scale scheduling problems
- A graph formulation of a school scheduling algorithm
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- A new line of attack on the dichotomy conjecture
- A new tractable class of constraint satisfaction problems
- A polynomial-time algorithm for near-unanimity graphs
- A retraction problem in graph theory
- Absolute Retracts and Varieties of Reflexive Graphs
- Absolute planar retracts and the four colour conjecture
- Absolute reflexive retracts and absolute bipartite retracts
- Absolute retracts of bipartite graphs
- Acyclic Homomorphisms and Circular Colorings of Digraphs
- Applications of product colouring
- Aspects of structural combinatorics. (Graph homomorphisms and their use)
- Bi‐arc graphs and the complexity of list homomorphisms
- Characterising tractable constraints
- Chromatically optimal rigid graphs
- Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection
- Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
- Classifying the Complexity of Constraints Using Finite Algebras
- Closed systems of functions and predicates
- Closure properties of constraints
- Colorings and homomorphisms of degenerate and bounded degree graphs
- Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
- Complexity classifications of Boolean constraint satisfaction problems
- Complexity of tree homomorphisms
- Computational Complexity of Compaction to Reflexive Cycles
- Conjunctive-query containment and constraint satisfaction
- Counting graph homomorphisms
- Cuts and bounds
- Decomposition by clique separators
- Dichotomies for classes of homomorphism problems involving unary functions
- Digraph matrix partitions and trigraph homomorphisms
- Dualities for Constraint Satisfaction Problems
- Duality and Polynomial Testing of Tree Homomorphisms
- Duality theorems for finite structures (characterising gaps and good characterisations)
- Efficient characterizations of \(n\)-chromatic absolute retracts
- Expander graphs and their applications
- Finite posets and topological spaces in locally finite varieties
- First-order Definable Retraction Problems for Posets and Reflexive Graphs
- Folding
- Forbidden lifts (NP and CSP for combinatorialists)
- From graph coloring to constraint satisfaction: there and back again
- Full Constraint Satisfaction Problems
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- Generalized Majority-Minority Operations are Tractable
- Generalized colouring (matrix partitions) of cographs
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
- Graph products, Fourier analysis and spectral techniques
- Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
- Handbook of constraint programming.
- Hereditarily hard \(H\)-colouring problems
- Homomorphisms in graph property testing
- Independent sets in graph powers are almost contained in juntas
- Interval digraphs: An analogue of interval graphs
- Linear time low tree-width partitions and algorithmic consequences
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- List Partitions
- List homomorphisms and circular arc graphs
- List homomorphisms of graphs with bounded degrees
- List homomorphisms to reflexive graphs
- List matrix partitions of chordal graphs
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- Many Facets of Dualities
- Mathematical Foundations of Computer Science 2003
- Matrix partitions of perfect graphs
- Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
- Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
- Minimum Cost Homomorphisms to Reflexive Digraphs
- Minimum cost and list homomorphisms to semicomplete digraphs
- Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs
- Near-Unanimity Functions and Varieties of Reflexive Graphs
- Networks of constraints: Fundamental properties and applications to picture processing
- Nombre chromatique et plus longs chemins d'un graphe
- Note on projective graphs
- On Dinur’s proof of the PCP theorem
- On classes of relations and graphs determined by subobjects and factorobjects
- On colorings of graphs without short cycles
- On digraph coloring problems and treewidth duality
- On realizations of point determining graphs, and obstructions to full homomorphisms
- On sentences which are true of direct unions of algebras
- On sparse graphs with given colorings and homomorphisms.
- On the Structure of Polynomial Time Reducibility
- On the algebraic structure of combinatorial problems
- On the complexity of H-coloring
- On the complexity of colouring by superdigraphs of bipartite graphs
- Partitioning chordal graphs into independent sets and cliques
- Polynomial graph-colorings
- Precoloring Extension III: Classes of Perfect Graphs
- Precoloring extension on chordal graphs
- Precoloring extension. I: Interval graphs
- Products of absolute retracts
- Projectivity and independent sets in powers of graphs
- Proof verification and the hardness of approximation problems
- Reflection positivity, rank connectivity, and homomorphism of graphs
- Retractions onto series-parallel posets
- Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
- Star-cutsets and perfect graphs
- Structural Properties of Sparse Graphs
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The Complexity of Colouring by Semicomplete Digraphs
- The Complexity of the Extendibility Problem for Finite Posets
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The NP-completeness column: An ongoing guide
- The PCP theorem by gap amplification
- The Ramsey number R(3, t) has order of magnitude t2/log t
- The complexity of \(H\)-colouring of bounded degree graphs
- The complexity of satisfiability problems
- The complexity of the list homomorphism problem for graphs
- The core of a graph
- The effect of two cycles on the complexity of colourings by directed graphs
- The list partition problem for graphs
- The strong perfect graph theorem
- Tractability and learnability arising from algebras with few subpowers
- Tree-depth, subgraph coloring and homomorphism bounds
- Two algorithms for general list matrix partitions
- Varieties with few subalgebras of powers
- Zur algebraischen Begründung der Graphentheorie. I
- H-coloring dichotomy revisited
Cited in
(36)- In praise of homomorphisms
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- scientific article; zbMATH DE number 6724468 (Why is no real title available?)
- Graph partitions with prescribed patterns
- Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
- Tractability in constraint satisfaction problems: a survey
- The power of linear programming for general-valued CSPs
- ON THE COMPLEXITY OF SOME COLORING GAMES
- The complexity of conservative valued CSPs
- Binary constraint satisfaction problems defined by excluded topological minors
- scientific article; zbMATH DE number 1390075 (Why is no real title available?)
- Backdoor sets for CSP
- Connected obstructions to full graph homomorphisms
- The \(C_{k}\)-extended graft construction
- Beyond Boolean surjective VCSPs
- From graph coloring to constraint satisfaction: there and back again
- \(H\)-coloring degree-bounded (acyclic) digraphs
- Dualities in full homomorphisms
- A tetrachotomy of ontology-mediated queries with a covering axiom
- Binary simple homogeneous structures are supersimple with finite rank
- Hybrid tractable classes of constraint problems
- Necessary conditions for tractability of valued CSPs
- A new line of attack on the dichotomy conjecture
- NP-Completeness of Spreading Colored Points
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- A Galois connection for valued constraint languages of infinite size
- On planar valued CSPs
- The 1-Color Problem and the Brylawski Model
- Homogeneous 1-based structures and interpretability in random structures
- Reflexive graphs with near unanimity but no semilattice polymorphisms
- The Parallel Complexity of Coloring Games
- The complexity of valued CSPs
- The complexity of grid coloring
- A complexity dichotomy for signed \(\mathbf{H}\)-colouring
- Obstructions to partitions of chordal graphs
- On constraints and dividing in ternary homogeneous structures
This page was built for publication: Colouring, constraint satisfaction, and complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458466)
