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
Artikel, Zweitveröffentlichung, Verlagsversion
 | Es ist eine neuere Version dieses Eintrags verfügbar. |
Kurzbeschreibung (Abstract)
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.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2024 |
| Autor(en): | Bachtler, Oliver ; Heinrich, Irene |
| Art des Eintrags: | Zweitveröffentlichung |
| Titel: | Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width |
| Sprache: | Englisch |
| Publikationsjahr: | 9 Februar 2024 |
| Ort: | Darmstadt |
| Publikationsdatum der Erstveröffentlichung: | 2023 |
| Ort der Erstveröffentlichung: | New York |
| Verlag: | Wiley |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Journal of Graph Theory |
| Jahrgang/Volume einer Zeitschrift: | 104 |
| (Heft-)Nummer: | 2 |
| DOI: | 10.26083/tuprints-00024690 |
| URL / URN: | https://tuprints.ulb.tu-darmstadt.de/24690 |
| Zugehörige Links: | |
| Herkunft: | Zweitveröffentlichung DeepGreen |
| Kurzbeschreibung (Abstract): | 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. |
| Freie Schlagworte: | cubic graph, girth, path‐width, unavoidable structure |
| Status: | Verlagsversion |
| URN: | urn:nbn:de:tuda-tuprints-246900 |
| Sachgruppe der Dewey Dezimalklassifikatin (DDC): | 500 Naturwissenschaften und Mathematik > 510 Mathematik |
| Fachbereich(e)/-gebiet(e): | 04 Fachbereich Mathematik 04 Fachbereich Mathematik > Didaktik 04 Fachbereich Mathematik > Optimierung |
| Hinterlegungsdatum: | 09 Feb 2024 13:37 |
| Letzte Änderung: | 12 Mär 2024 07:55 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
Verfügbare Versionen dieses Eintrags
- Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width. (deposited 09 Feb 2024 13:37) [Gegenwärtig angezeigt]
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum