3 papers
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…
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…
cs.DM2025
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…