K4-free graphs as a free algebra
Mostra el registre complet de l'element
|
Visualització
 (513.0Kb)
|
|
|
|
|
|
|
Cosme i Llópez, Enric; Pous, Damien
|
|
Aquest document és un/a article, creat/da en: 2017
|
|
|
|
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 equationa lpresentation and we prove it complete: two terms from the syntax are congruent if and only if they denote the same graph. |
|
|
Veure al catàleg Trobes
|
|
|
Aquest element apareix en la col·lecció o col·leccions següent(s)
Mostra el registre complet de l'element
