e-space
Manchester Metropolitan University's Research Repository

    Adjoint functors and tree duality

    Foniok, J and Tardif, C (2009) Adjoint functors and tree duality. Discrete Mathematics and Theoretical Computer Science, 11. ISSN 1365-8050

    [img]
    Preview

    Available under License Creative Commons Attribution.

    Download (256kB) | Preview

    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 H also has tree duality, and we derive a family of tree obstructions for 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.

    Impact and Reach

    Statistics

    Activity Overview
    6 month trend
    93Downloads
    6 month trend
    265Hits

    Additional statistics for this dataset are available via IRStats2.

    Repository staff only

    Edit record Edit record