Duality theorems for finite structures (characterising gaps and good characterisations)
From MaRDI portal
Publication:1850486
DOI10.1006/jctb.2000.1970zbMath1024.05078OpenAlexW1986537785MaRDI QIDQ1850486
Claude Tardif, Jaroslav Nešetřil
Publication date: 10 December 2002
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/6e4eddf4d6671c37537bb5d1c9623353b62e8531
Combinatorics in computer science (68R05) Structural characterization of families of graphs (05C75) Relational systems, laws of composition (08A02)
Related Items
In praise of homomorphisms, On the density of trigraph homomorphisms, Oriented expressions of graph properties, Constraint satisfaction, irredundant axiomatisability and continuous colouring, Fractal property of the graph homomorphism order, No finite-infinite antichain duality in the homomorphism poset of directed graphs, Dualities and dual pairs in Heyting algebras, On infinite-finite duality pairs of directed graphs, NP for Combinatorialists, On Finite Maximal Antichains in the Homomorphism Order, Gaps in full homomorphism order, A new line of attack on the dichotomy conjecture, Specifying graph languages with type graphs, On digraph coloring problems and treewidth duality, Majority constraints have bounded pathwidth duality, Generalised dualities and maximal finite antichains in the homomorphism order of relational structures, Forbidden lifts (NP and CSP for combinatorialists), Majority functions on structures with finite duality, Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities, On tension-continuous mappings, On the order of countable graphs, On nowhere dense graphs, Tension continuous maps -- their structure and applications, Many Facets of Dualities, A note on random homomorphism from arbitrary graphs to \(\mathbb{Z}\), Interleaved adjoints of directed graphs, Colouring, constraint satisfaction, and complexity, Algebra and the Complexity of Digraph CSPs: a Survey, Digraph functors which admit both left and right adjoints, On the General Coloring Problem, A dualistic approach to bounding the chromatic number of a graph, On the restricted homomorphism problem, Regular families of forests, antichains and duality pairs of relational structures, Topology of Hom complexes and test graphs for bounding chromatic number, Homomorphisms of random paths, First order properties on nowhere dense structures, Tree-depth, subgraph coloring and homomorphism bounds, Universal partial order represented by means of oriented trees and other simple graphs, Path homomorphisms, graph colorings, and boolean matrices, The homomorphism lattice induced by a finite algebra, CoReS: a tool for computing core graphs via SAT/SMT solvers, Graph partitions with prescribed patterns, Obstructions to locally injective oriented improper colourings, Connected obstructions to full graph homomorphisms, Duality pairs and homomorphisms to oriented and unoriented cycles, Unnamed Item, Finite paths are universal, Dualities in full homomorphisms, All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms), A surprising permanence of old motivations (a not-so-rigid story), Splittings in varieties of logic, Chromatic numbers and products, Dualities for Constraint Satisfaction Problems, Cuts and bounds, Density via duality.
Cites Work
- Unnamed Item
- Unnamed Item
- Symmetric graphs and interpretations
- On the complexity of H-coloring
- Color-families are dense
- On classes of relations and graphs determined by subobjects and factorobjects
- Fractional multiples of graphs and the density of vertex-transitive graphs
- Lattices arising in categorial investigations of Hedetniemi's conjecture
- Symmetric relations (undirected graphs) with given semigroups
- The Homomorphism Structure of Classes of Graphs
- Duality and Polynomial Testing of Tree Homomorphisms
- Path homomorphisms
- Paths, Trees, and Flowers
- Operations with structures
