An improved spectral lower bound of treewidth

Tatsuya Gima, Tesshu Hanaka, Kohei Noro +2

We show that for every $n$-vertex graph with at least one edge, its treewidth is greater than or equal to $n{\lambda }_2/(\Delta +{\lambda }_2)-1$, where $\Delta$ and ${\lambda }_2$ are the maximum degree a…