3 papers
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…
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…