6533b860fe1ef96bd12c402f
RESEARCH PRODUCT
K4-free Graphs as a Free Algebra
Enric Cosme-llópezDamien Poussubject
Completeness000 Computer science knowledge general worksGraph minors[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Graph theoryTree decompositions[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Àlgebra universalUniversal Algebra[INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]Computer Science::Discrete MathematicsComputer ScienceAxiomatisation[INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]description
International audience; Graphs of treewidth at most two are the ones excluding the clique with four vertices (K4) as a minor, or equivalently, the graphs whose biconnected components are series-parallel. We turn those graphs into a finitely presented free algebra, answering positively a question by Courcelle and Engelfriet, in the case of treewidth two. First we propose a syntax for denoting these graphs: in addition to parallel composition and series composition, it suffices to consider the neutral elements of those operations and a unary transpose operation. Then we give a finite equational presentation and we prove it complete: two terms from the syntax are congruent if and only if they denote the same graph.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2017-08-21 |