文章基本信息

标题：K4-free Graphs as a Free Algebra
本地全文：下载
作者：Enric Cosme Ll{\'o}pez ; Damien Pous
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：83
页码：76:1-76:14
DOI：10.4230/LIPIcs.MFCS.2017.76
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Universal Algebra; Graph theory; Axiomatisation; Tree decompositions; Graph minors