K4-free graphs as a free algebra

K4-free graphs as a free algebra

DSpace Repository

K4-free graphs as a free algebra

Show full item record

View       (513.0Kb)

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

This item appears in the following Collection(s)

Show full item record

Search DSpace

Advanced Search