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

DOI10.1002/JGT.22964MaRDI QIDQ6094029zbMATH OpenOpenAlexFDO

Authors Oliver Bachtler, Irene Heinrich

Publication date 9 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/2010.08373

zbMATH Keywords

cubic graphgirthpath-widthunavoidable structure

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Abstract: We present an interactive framework that, given a membership test for a graph class $mathcalG$ and a number $k$, finds and tests unavoidable sets for the class of graphs in $mathcalG$ of path-width at most $k$. We put special emphasis on the case that $mathcalG$ 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 yields highly efficient pruning techniques. Using this framework we determine all extremal girth values of cubic graphs of path-width $k$ for all $kin3,dots,10$. Moreover, we determine all smallest graphs which take on these extremal girth values. As a further application of our framework we characterise the extremal cubic graphs of path-width 3 and girth 4.

Recommendations

• Pathwidth of cubic graphs and exact algorithms
• Optimal unavoidable sets of types of 3-paths for planar graphs of given girth
• The structure of obstructions to treewidth and pathwidth
• Minimal unavoidable sets of cycles in plane graphs
• Constructive linear time algorithms for branchwidth

Cites work

• scientific article; zbMATH DE number 3046496 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• A variant of a recursively unsolvable problem
• An introduction to the discharging method via graph coloring
• Cycle decompositions of pathwidth-6 graphs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Girth and treewidth
• Graph minors. XX: Wagner's conjecture
• Graph theory
• House of Graphs: a database of interesting graphs
• Introduction to local certification
• Knot diagrams of treewidth two
• Locally checkable proofs in distributed computing
• Proof labeling schemes
• Recent developments in graph Ramsey theory
• The complexity of first-order and monadic second-order logic revisited
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth computations. II. Lower bounds
• Unavoidable induced subgraphs in large graphs with no homogeneous sets

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6094029)