A finite presentation of graphs of treewidth at most three - Laboratoire d'excellence en Mathématiques et informatique fondamentale de Lyon Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2024

A finite presentation of graphs of treewidth at most three

Résumé

We provide a finite equational presentation of graphs of treewidth at most three, solving an instance of an open problem by Courcelle and Engelfriet. We use a syntax generalising series-parallel expressions, denoting graphs with a small interface. We introduce appropriate notions of connectivity for such graphs (components, cutvertices, separation pairs). We use those concepts to analyse the structure of graphs of treewidth at most three, showing how they can be decomposed recursively, first canonically into connected parallel components, and then non-deterministically. The main difficulty consists in showing that all non-deterministic choices can be related using only finitely many equational axioms.
Fichier principal
Vignette du fichier
tw3.pdf (752.72 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
licence : CC BY - Paternité

Dates et versions

hal-04560570 , version 1 (26-04-2024)

Licence

Paternité

Identifiants

Citer

Amina Doumane, Samuel Humeau, Damien Pous. A finite presentation of graphs of treewidth at most three. 2024. ⟨hal-04560570⟩
0 Consultations
1 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More