On the structure of graphs with path-width at most two. (English) Zbl 1289.05443

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

Stud. Sci. Math. Hung. 49, No. 2, 211-222 (2012).

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.

Reviewer: Michael Hager (Leonberg)

MSC:

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

Keywords:

path-width; excluded minor; block