TU Darmstadt / ULB / TUprints

Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width

Bachtler, Oliver ; Heinrich, Irene (2024)
Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width.
In: Journal of Graph Theory, 2023, 104 (2)
doi: 10.26083/tuprints-00024690
Article, Secondary publication, Publisher's Version

[img] Text
Copyright Information: CC BY-NC 4.0 International - Creative Commons, Attribution NonCommercial.

Download (1MB)
Item Type: Article
Type of entry: Secondary publication
Title: Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width
Language: English
Date: 9 February 2024
Place of Publication: Darmstadt
Year of primary publication: 2023
Place of primary publication: New York
Publisher: Wiley
Journal or Publication Title: Journal of Graph Theory
Volume of the journal: 104
Issue Number: 2
DOI: 10.26083/tuprints-00024690
Corresponding Links:
Origin: Secondary publication DeepGreen

Let G be a class of graphs with a membership test, k∈N , and let Gk be the class of graphs in G of path-width at most k. We present an interactive framework that finds an unavoidable set for Gk, which is a set of graphs U such that any graph in Gk contains an isomorphic copy of a graph in U. At the core of our framework is an algorithm that verifies whether a set of graphs is, indeed, unavoidable for Gk. While obstruction sets are well-studied, so far there is no general theory or algorithm for finding unavoidable sets. In general, it is undecidable whether a finite set of graphs is unavoidable for a given graph class. However, we give a criterion for termination: our algorithm terminates whenever G is locally checkable of bounded maximum degree and U is a finite set of connected graphs. For example, l-regular graphs, l-colourable graphs, and H-free graphs are locally checkable classes. We put special emphasis on the case that G is the class of cubic graphs and tailor the algorithm to this case. In particular, we introduce the new concept of high-degree-first path-decompositions, which enables highly efficient pruning techniques. We exploit our framework to prove a new lower bound on the path-width of cubic graphs. Moreover, we determine the extremal girth values of cubic graphs of path-width for all and all smallest graphs which take on these extremal girth values. Further, we present a new constructive characterisation of the extremal cubic graphs of path-width 3 and girth 4.

Uncontrolled Keywords: cubic graph, girth, path‐width, unavoidable structure
Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-246900
Classification DDC: 500 Science and mathematics > 510 Mathematics
Divisions: 04 Department of Mathematics > Didactics and Pedagogy of Mathematics
04 Department of Mathematics > Optimization
Date Deposited: 09 Feb 2024 13:37
Last Modified: 11 Apr 2024 07:43
SWORD Depositor: Deep Green
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/24690
PPN: 517021870
Actions (login required)
View Item View Item