On digraph coloring problems and treewidth duality

DOI10.1016/j.ejc.2007.11.004zbMath1160.05024OpenAlexW2003272326MaRDI QIDQ2427534

Albert Atserias

Publication date: 13 May 2008

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2007.11.004

zbMATH Keywords

CSPconstraint satisfaction problemcomputable listingdigraph colouring problemfinitary tree dualitytemplate structurestight functiontractable CSPstreewidth duality

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (26)

Dualities and algebras with a near-unanimity term ⋮ CSP for binary conservative relational structures ⋮ Constraint satisfaction, irredundant axiomatisability and continuous colouring ⋮ Dualities and dual pairs in Heyting algebras ⋮ Obstructions to partitions of chordal graphs ⋮ Relativised homomorphism preservation at the finite level ⋮ Generalised dualities and maximal finite antichains in the homomorphism order of relational structures ⋮ Low-level dichotomy for quantified constraint satisfaction problems ⋮ Many Facets of Dualities ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ Colouring, constraint satisfaction, and complexity ⋮ Dismantlability, connectedness, and mixing in relational structures ⋮ Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs ⋮ Quasi-equational bases for graphs of semigroups, monoids and groups. ⋮ The treewidth of line graphs ⋮ Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality ⋮ Graph partitions with prescribed patterns ⋮ Some tractable instances of interval data minmax regret problems ⋮ The complexity of satisfiability problems: Refining Schaefer's theorem ⋮ Unnamed Item ⋮ An Efficient Partitioning Oracle for Bounded-Treewidth Graphs ⋮ Partially ordered connectives and monadic monotone strict NP ⋮ Dualities for Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ Matrix Partitions with Finitely Many Obstructions ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• On the expressive power of Datalog: tools and a case study.
• Bounded width problems and algebras
• Lower bounds on monotone complexity of the logical permanent
• On the complexity of H-coloring
• Chromatically optimal rigid graphs
• Polynomial graph-colorings
• Graph searching and a min-max theorem for tree-width
• Datalog vs first-order logic
• Conjunctive-query containment and constraint satisfaction
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Complexity of tree homomorphisms
• Aspects of structural combinatorics. (Graph homomorphisms and their use)
• First-order Definable Retraction Problems for Posets and Reflexive Graphs
• On preservation under homomorphisms and unions of conjunctive queries
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Duality and Polynomial Testing of Tree Homomorphisms
• The complexity of satisfiability problems
• A Characterisation of First-Order Constraint Satisfaction Problems
• On sufficient conditions for unsatisfiability of random formulas

This page was built for publication: On digraph coloring problems and treewidth duality