- DSpace Home
- Investigació
- e-prints
- 12 - Matemàtiques
- View Item
K4-free graphs as a free algebra
|
View
|
| Cosme i Llópez, Enric; Pous, Damien | |||
| This document is a artículoDate2017 | |||
|
Este documento está disponible también en : http://hdl.handle.net/10550/69206 |
|||
|
|||
| 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. | |||
|
Cosme i Llópez, Enric Pous, Damien 2017 K4-free graphs as a free algebra 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) 83 76 76:1 76:14 |
|||
| https://doi.org/10.4230/LIPIcs.MFCS.2017.76 |
This item appears in the following Collection(s)
-
12 - Matemàtiques [277]