On the structure of graphs with path-width at most two

DOI10.1556/SSCMATH.49.2012.2.1200MaRDI QIDQ2915439zbMATH OpenOpenAlexFDO

Authors János Barát, Péter Hajnal, Aifeng Yang, Yixun Lin

Publication date 17 September 2012

Published in Studia Scientiarum Mathematicarum Hungarica (Search for Journal in Brave)

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

zbMATH Keywords

blockexcluded minorpath-width

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: Nancy G. Kinnersley and Michael A. Langston has determined the excluded minors for the class of graphs with path-width at most two by computer. Their list consisted of 110 graphs. Such a long list is difficult to handle and gives no insight to structural properties. We take a different route, and concentrate on the building blocks and how they are glued together. In this way, we get a characterization of 2-connected and 2-edge-connected graphs with path-width at most two. Along similar lines, we sketch the complete characterization of graphs with path-width at most two.

Review text

\textit{N.~G.~Kinnersley} and \textit{M.~A.~Langston} [Discrete Appl.\ Math. 54, No. ~2--3, 169--213 (1994; Zbl 0941.68590)] used a computer search to characterize the class of graphs with path-width at most two. There the excluded minor list consists of 110 graphs. The authors here concentrate on the building blocks of the graphs with path-width at most two and how they are glued together. The main result is that for 2-connected graphs with path-width at most two there exist only three excluded minors. So the authors get a short and compact characterization of 2-connected and 2-edge-connected graphs with path-width at most two.

Recommendations

• Operations which preserve path-width at most two
• On 3-connected graphs of path-width at most three
• Graph Minors I: A Short Proof of the Path-width Theorem
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Excluding a long double path minor

Cited in

(11)

• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• On the geometric Ramsey number of outerplanar graphs
• Seymour's conjecture on 2-connected graphs of large pathwidth
• Operations which preserve path-width at most two
• On 3-connected graphs of path-width at most three
• Posets with cover graph of pathwidth two have bounded dimension
• Digraphs of bounded width
• Characterizing width two for variants of treewidth
• Graphs with few paths of prescribed length between any two vertices
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• B0-VPG Representation of AT-free Outerplanar Graphs

This page was built for publication: On the structure of graphs with path-width at most two

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