×

zbMATH — the first resource for mathematics

On the structure of graphs with path-width at most two. (English) Zbl 1289.05443
N. G. Kinnersley and 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.

MSC:
05C83 Graph minors
05C75 Structural characterization of families of graphs
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI arXiv