2 papers
math.CO2026
A Low-Diameter Nash-Williams--Tutte Theorem
Pin-Hsian Lee, Peng-Ting Lin, Meng-Tsung Tsai +1
The Nash-Williams--Tutte theorem characterizes the existence of edge-disjoint spanning trees by a condition on every vertex partition. We prove that, for simple graphs, the sam…
cs.CC2026
Determining the Outerthickness of Graphs Is NP-Hard
Pin-Hsian Lee, Te-Cheng Liu, Meng-Tsung Tsai
We give a short, self-contained, and easily verifiable proof that determining the outerthickness of a general graph is NP-hard. This resolves a long-standing open problem on the co…