2025/05/29 by Naoki Matsumoto, Matsumoto, Naoki, Takamasa Yashima +2 · 1 citation
Computer Science · Mathematics · #05C10 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2505.23162
openalex publication_date 2025/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A long-standing conjecture by Albertson and Berman in 1979 states that every planar graph of order n has an induced forest with at least \lceil (n)/(2) \rceil vertices. As a variant of this conjecture, Chappell conjectured that every planar graph of order n has an induced linear forest with at least \lceil (4n)/(9) \rceil vertices. As a partial solution to the conjecture, Pelsmajer in 2004 proved that every outerplanar graph of order n has an induced linear forest with at least \lceil (4n+2)/(7)\rceil vertices and this bound is sharp. In this paper, we investigate the order of induced subgraphs with a given pathwidth in outerplanar graphs. The above result of Pelsmajer implies that every outerplanar graph of order n has an induced subgraph with pathwidth at most 1 and at least \lceil (4n+2)/(7)\rceil vertices. We extend this to obtain a result on the maximum order of induced subgraphs with a given pathwidth in an outerplanar graph. We also give its upper bound, which generalizes Pelsmajer's construction.