15 Conclusion and open problems
For twenty years, the bound \(\frac n6+o(n)\) of Fomin and Høie (Fomin and Høie 2006) was the best bound on the pathwidth of \(n\)-vertex graphs of maximum degree \(3\), and many exact algorithms stated their running times through it. We replaced the bisection behind it by a threshold sweep through correlated Gaussian labels. Comparing each star with an ideal star, and switching from inner to outer frontiers at the median, brought the bound down to \(c_{3}n+o(n)\) with \(c_{3}=\frac3{4\pi}\arccos\frac56\approx0.1398\). A charging scheme certified by computer and a bootstrap to large degrees extended the method to all graphs, with the coefficient \(\frac14\) in place of \(\frac13\) at degree \(4\) and the bound \(\frac7{48}m\) per edge in place of \(\frac{13}{75}m\). The decompositions can be computed in polynomial time. This solves the open problem of van Rooij (Rooij 2011 Open Problem 14.2), which asks for tree decompositions of cubic graphs of width \(c_tn+o(n)\), for some constant \(c_t<\frac16\), computable in polynomial time: we obtain \(c_t=c_{3}\), even for path decompositions. With the new decompositions, many exact algorithms whose running times depend on these widths have smaller running-time bounds (Part II). We close with the questions that the Gaussian sweep leaves open.
The constant for maximum degree \(3\).
What is the smallest constant \(c\) such that every graph of maximum degree \(3\) has pathwidth at most \(cn+o(n)\)? It lies in \([0.1032,c_{3}]\), and the lower end comes from random cubic graphs (Lichev and Mitsche 2023). Since \(c_{3}\) is exactly what the median-switched sweep gives on cubic graphs of large girth, an improvement must change the rule at threshold zero, for instance by letting a vertex above the threshold carry the crossing edges of all lower neighbors whose only upper neighbor it is. On the ideal wave, the centered Gaussian vector on the rooted tree \(T_2\) (root \(o\) with three children \(u_1,u_2,u_3\), each with two children) with covariance \(2^{-d/2}(1+\frac d3)\) at distance \(d\), which is the limit of our labels on cubic graphs of large girth, this rule saves \(3p_{\mathrm{ch}}\) per vertex at threshold zero, where \(p_{\mathrm{ch}}=0.00252477819777\ldots\) (certified in interval arithmetic) is the probability that \(u_1\) and \(u_2\) both have \(o\) as their only neighbor above zero.1
Conjecture 15.1 (ideal-wave bound). Every cubic graph \(G\) satisfies \(\mathop{\mathrm{pw}}(G)\le(c_{3}-3p_{\mathrm{ch}})n+o(n)\), where \(c_{3}-3p_{\mathrm{ch}}=0.13224778941\ldots\).
Proving it, or any improvement of \(c_{3}\), seems to require a quantitative stability version of the star comparison.
Maximum degree \(4\).
For maximum degree \(3\), the median switch lowers the coefficient of the plain sweep, the maximum \(F_3\approx0.1402\) of the ideal \(3\)-star function, to the value \(c_{3}\) of that function at threshold zero. For maximum degree \(4\) we prove \(F_4n+o(n)\), where \(F_4\approx0.2458\) is the maximum of the ideal \(4\)-star function; its value at threshold zero is \(0.2423\). Is there a rule at threshold zero whose width bound on \(4\)-regular graphs approaches \(0.2423n\)? Our median switch, analyzed star by star, cannot approach \(0.2423\): the switch quantity \(\Psi\) of a vertex with four neighbors of degree \(4\) can equal \(\frac14>F_4\) (see the discussion after Lemma A.10). It does give the bound \(c_{3}n_3+0.2627\,n_4\) (Theorem 8.2), which is smaller than the bounds of Theorem 7.1 when \(n_4<\frac{F_3-c_{3}}{0.0052}\,n_3\approx0.0646\,n_3\). This form of the method cannot lower \(0.2627\) much below \(0.2618\) (Remark A.15).
Degree \(6\) and the bound per edge.
Can the coefficient \(a_6=\frac7{16}\) of Theorem 1.3 be lowered? For degrees \(6\) and more, all our coefficients come from the bootstrap. The constant \(\frac7{48}\) of Corollary 1.4 is \(2a_6/6\), and every other ratio \(2a_d/d\) is at most \(\frac{113}{784}\), attained at \(d=7\) (proof of Corollary 1.4); so a better coefficient at degree \(6\) alone would lower the bound per edge.
Treewidth.
For any of the classes considered here, is the worst-case coefficient of treewidth smaller than that of pathwidth? The Gaussian sweep produces path decompositions, and it has given us no gain specific to treewidth at leading order.
References
Footnotes
This is the ideal-tree value of the “isolated helper” event of Lichev and Mitsche (Lichev and Mitsche 2023); the number \(0.002818666\) printed there is not this value, and its authors have confirmed that it was not accurate (L. Lichev and D. Mitsche, personal communication, 2026).↩︎