The following paper has been published:
El siguiente artículo ha sido publicado:
El següent article ha sigut publicat:

E. Cosme Llópez, Damien Pous.
K_4-free graphs as a free algebra.
42nd International Symposium on Mathematical Foundations of Computer Science, Art. No. 76, 14 pp., LIPIcs. Leibniz Int. Proc. Inform., 83, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017.

doi: 10.4230/LIPIcs.MFCS.2017.76

Abstract:

Graphs of treewidth at most two are the ones excluding the clique with four vertices as a minor. Equivalently, they are the graphs whose biconnected components are series-parallel.
 

We turn those graphs into a free algebra, answering positively a question by Courcelle and Engelfriet, in the case of treewidth two. First we propose a syntax for denoting them: in addition to series and parallel compositions, 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.’

2020 Mathematics Subject Classification: 68R10, 68Q45.

Keywords: universal Algebra, graph theory, axiomatisation, graph minors.