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…
math.CO2026
Characterization and chromatic number of triangle-free graphs with diameter 2
Akihiro Higashitani, Diogo Kendy Matsumoto, Naoki Matsumoto
In this paper, we consider triangle-free graphs with diameter 2. If a triangle-free graph with diameter 2 is not isomorphic to a star, then the radius of is also 2, where s…
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…