Showing cs.DMShow all
2 papers · 1 filter
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…