Adjoint functors and tree duality

zbMATH Open1196.05035arXiv0805.2978MaRDI QIDQ3575461FDOQ3575461

Claude Tardif, Jan Foniok

Publication date: 27 July 2010

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.

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

zbMATH Keywords

adjoint functorconstraint satisfactiontree duality

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Adjoint functors (universal constructions, reflective subcategories, Kan extensions, etc.) (18A40)

Cited In (7)

• On cylindrical graph construction and its applications
• Hedetniemi's conjecture and adjoint functors in thin categories
• Title not available (Why is that?)
• Hedetniemi's conjecture and dense Boolean lattices
• Adjoint-triangle theorems for conservative functors
• Digraph functors which admit both left and right adjoints
• Interleaved adjoints of directed graphs

This page was built for publication: Adjoint functors and tree duality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3575461)