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

DOI10.1002/JGT.22964zbMATH Open1522.05463arXiv2010.08373OpenAlexW3093109028MaRDI QIDQ6094029FDOQ6094029

Authors: Oliver Bachtler, Irene Heinrich 

Publication date: 9 October 2023

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

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.

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

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

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)

Cites Work

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

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)