3 papers
cs.DM2026
Large induced subgraph with a given pathwidth in outerplanar graphs
Naoki Matsumoto, Takamasa Yashima, Hikaru Yokoi
A long-standing conjecture by Albertson and Berman in 1979 states that every planar graph of order has an induced forest with at least vertices. As…
cs.DM2025
Contributions to conjectures on planar graphs: Induced Subgraphs, Treewidth, and Dominating Sets
Kengo Enami, Naoki Matsumoto, Takamasa Yashima
Two of the most prominent unresolved conjectures in graph theory, the Albertson-Berman conjecture and the Matheson-Tarjan conjecture, have been extensively studied by many research…
math.CO2025
A generalization of an ear decomposition and k-trees in highly connected star-free graphs
Shun-ichi Maezawa, Kenta Ozeki, Masaki Yamamoto +1
In this paper, we introduce a generalized version of an ear decomposition, called a -spider decomposition, for -connected star-free graphs with . Its application en…