On infinite-finite duality pairs of directed graphs

DOI10.1007/S11083-012-9278-9zbMath1276.05053arXiv1203.1257OpenAlexW2951827106MaRDI QIDQ382885

Gábor Tardos, Claude Tardif, Péter L. Erdős

Publication date: 22 November 2013

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.1257

zbMATH Keywords

graph homomorphismregular languagesconstraint satisfaction problemduality pairsgeneral relational structuresnondeterministic finite automaton

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• No finite-infinite antichain duality in the homomorphism poset of directed graphs
• Regular families of forests, antichains and duality pairs of relational structures
• On classes of relations and graphs determined by subobjects and factorobjects
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• Caterpillar Dualities and Regular Languages
• Unnamed Item

This page was built for publication: On infinite-finite duality pairs of directed graphs