K4-free graphs as a free algebra
NAGIOS: RODERIC FUNCIONANDO

# K4-free graphs as a free algebra

 dc.contributor.author Cosme i Llópez, Enric dc.contributor.author Pous, Damien dc.date.accessioned 2019-02-27T14:25:37Z dc.date.available 2019-02-27T14:25:37Z dc.date.issued 2017 dc.identifier.uri http://hdl.handle.net/10550/69206 dc.description.abstract 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. dc.language.iso eng dc.relation.ispartof 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), 2017, vol. 83, num. 76, p. 76:1-76:14 dc.rights.uri info:eu-repo/semantics/openAccess dc.source 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 dc.subject Àlgebra universal dc.title K4-free graphs as a free algebra dc.type info:eu-repo/semantics/article dc.date.updated 2019-02-27T14:25:38Z dc.identifier.doi https://doi.org/10.4230/LIPIcs.MFCS.2017.76 dc.identifier.idgrec 130223

View       (513.0Kb)