Bachtler, Oliver ; Heinrich, Irene (2023)
Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width.
In: Journal of Graph Theory, 104 (2)
doi: 10.1002/jgt.22964
Article, Bibliographie
This is the latest version of this item.
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.
| Item Type: | Article |
|---|---|
| Erschienen: | 2023 |
| Creators: | Bachtler, Oliver ; Heinrich, Irene |
| Type of entry: | Bibliographie |
| Title: | Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width |
| Language: | English |
| Date: | 2023 |
| Place of Publication: | New York |
| Publisher: | Wiley |
| Journal or Publication Title: | Journal of Graph Theory |
| Volume of the journal: | 104 |
| Issue Number: | 2 |
| DOI: | 10.1002/jgt.22964 |
| Corresponding Links: | |
| 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. |
| Uncontrolled Keywords: | cubic graph, girth, path‐width, unavoidable structure |
| Classification DDC: | 500 Science and mathematics > 510 Mathematics |
| Divisions: | 04 Department of Mathematics 04 Department of Mathematics > Didactics and Pedagogy of Mathematics 04 Department of Mathematics > Optimization |
| Date Deposited: | 12 Mar 2024 07:55 |
| Last Modified: | 12 Mar 2024 07:55 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
Available Versions of this Item
-
Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width. (deposited 09 Feb 2024 13:37)
- Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width. (deposited 12 Mar 2024 07:55) [Currently Displayed]
 |
Send an inquiry |
Options (only for editors)
 |
Show editorial Details |
Drucken
Impressum