Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

Adjoint functors and tree duality

Abstract : A family T of digraphs is a complete set of obstructions for a digraph H if for an arbitrary digraph G the existence of a homomorphism from G to H is equivalent to the non-existence of a homomorphism from any member of T to G. A digraph H is said to have tree duality if there exists a complete set of obstructions T consisting of orientations of trees. We show that if H has tree duality, then its arc graph delta H also has tree duality, and we derive a family of tree obstructions for delta H from the obstructions for H. Furthermore we generalise our result to right adjoint functors on categories of relational structures. We show that these functors always preserve tree duality, as well as polynomial CSPs and the existence of near-unanimity functions.
Document type :
Journal articles
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-00988207
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Wednesday, May 7, 2014 - 3:58:17 PM
Last modification on : Thursday, May 27, 2021 - 1:54:05 PM
Long-term archiving on: : Thursday, August 7, 2014 - 11:36:19 AM

File

987-4374-2-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jan Foniok, Claude Tardif. Adjoint functors and tree duality. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, Vol. 11 no. 2 (2), pp.97--109. ⟨10.46298/dmtcs.458⟩. ⟨hal-00988207⟩

Share

Metrics

Record views

64

Files downloads

551