{"id":"arxiv/2611.05146","url":"https://arxiv.org/abs/2611.05146","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms","domain":"cs.DS","source":"arxiv","authors":["Serge Gaspers"],"reviews":0,"subject":"cs.DS","summary":"Using the bisection bound of Monien and Preis, Fomin and Høie proved in 2006 that every graph of maximum degree 3 on $n$ vertices has pathwidth at most $n/6+o(n)$. We prove that the pathwidth, bisection width and cutwidth of these graphs are at most $c_3 n+o(n)$, where $c_3=\\frac{3}{4π}\\arccos\\frac56\\approx0.1398$. For bisection width this improves the bound $n/6+o(n)$ of Monien and Preis (2006) and extends to all such graphs the bound that Lichev and Mitsche (2023) obtained for random cubic graphs. For maximum degree 4, we prove that bisection width and cutwidth are at most $n/3+o(n)$,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}