Spanning tree congestion of proper interval graphs
arXiv:2602.13756
Abstract
We show that the spanning tree congestion problem is NP-complete even on proper interval graphs with linear clique-width at most 4 and diameter 3. By slightly modifying the reduction, we also show that the problem is NP-complete on (general) graphs of diameter 2.
arXiv comment14 pages, 3 figures