1995/03/01 by Reinhard Diestel · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Graph minor #Interconnection Networks and Systems #Line graph #Mathematical analysis #Mathematics #Path (computing) #Pathwidth #Robertson–Seymour theorem #Upper and lower bounds #Voltage graph
paper · doi:10.1017/s0963548300001450
openalex publication_date 1995/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
Robertson and Seymour proved that excluding any fixed forest F as a minorimposes a bound on the path-width of a graph. We give a short proof of this, reobtaining the best possible bound of |F| – 2.