2009/10/26 by János Barát, Péter Hajnal, Peter I. Hajnal +6 · 1 citation
Computer Science · Mathematics · #05C75 #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #math.CO #msc:05C75 #msc:05C83
paper · pdf · doi:10.48550/arxiv.0910.4889
14 pages, 11 figures
arxiv created 2009/10/26 · openalex publication_date 2009/10/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
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.