Cubic Graph Pathwidth

Maximum Pathwidth of Cubic Graphs

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A path decomposition is a sequence of bags $B_1,\ldots,B_t\subseteq V(G)$ that covers the vertices, contains both endpoints of each edge in some bag, and makes $\{i:v\in B_i\}$ an interval for every vertex $v$. Its width is $\max_i|B_i|-1$; pathwidth is the minimum width. Maximize it over simple cubic graphs of each admissible even order $n$. [S1] [S2]

Statement recorded in the supplied source.

What is the maximum pathwidth of an n-vertex cubic graph? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Close the linear gap or determine the exact extremal pathwidth. [S1]

Short English statement

How large can pathwidth be among graphs of a fixed order in which every vertex has degree three?

Research attempt

Exact extremal question and chosen finite invariant.

The maximum is over all simple cubic graphs of a given admissible even order $n$, not just connected graphs from a named construction. The approach below expresses pathwidth by an ordering invariant, proves elementary bounds, and computes that invariant exactly on four small cubic examples. These examples are not an enumeration of all cubic graphs at their orders. The stronger asymptotic work recorded in [S2] is not reproduced; bibliographic verification limits are stated in [E1].

Pathwidth as the minimum exposed boundary.

For $S\subseteq V(G)$, set \[ b(S)=|\{v\in S:N(v)\not\subseteq S\}|. \] For an ordering $v_1,\ldots,v_n$, put $S_i=\{v_1,\ldots,v_i\}$. Then \[ \operatorname{pw}(G)=\min_{\text{orderings}}\max_{0\le i\le n}b(S_i). \] Here is a proof with the convention on width visible. From an ordering, use the bags $B_i=\{v_i\}\cup\{v\in S_{i-1}:N(v)\not\subseteq S_{i-1}\}$. The size is at most one plus the maximum boundary. Each edge $v_jv_i$ with $j<i$ is covered by $B_i$. A vertex occurs from its introduction through the introduction of its last neighbour, an interval. Thus the bags give a path decomposition of width at most the boundary maximum.

Conversely, order vertices by their first bag appearances, breaking ties arbitrarily. At a cut before the next vertex $w$, each earlier vertex having a later neighbour must still occur in the first bag of $w$: its interval starts earlier and extends at least to the first appearance of that later neighbour. The bag also contains $w$ itself. Hence its size is at least the boundary size plus one. This proves the reverse inequality, including cuts inside a tie of first appearances.

An exact subset recurrence.

Let $D(S)$ be the smallest possible maximum boundary over a sequence of prefixes ordering precisely the vertices in $S$, with every boundary measured relative to the full graph. Removing the last vertex gives \[ D(\varnothing)=0,\qquad D(S)=\min_{v\in S}\max\{D(S\setminus\{v\}),b(S)\}. \] Every ordering has a last vertex, and every optimal ordering of the smaller set extends by that vertex, so both directions of this recurrence are exact. In particular $D(V)=\operatorname{pw}(G)$. The $2^n$ states are expensive for large $n$, but a completed table proves optimality for a given finite graph rather than merely finding a good decomposition. Saving a predecessor also gives a witnessing ordering for its upper bound.

A universal elementary upper bound.

A greedy independent-set algorithm selects a vertex and deletes it and its neighbours, eliminating at most four vertices in a cubic graph at each step. It produces an independent set $I$ with $|I|\ge\lceil n/4\rceil$. Its complement $C$ is a vertex cover. The bags $C\cup\{u\}$, one for each $u\in I$, cover every edge: edges within $C$ occur in every bag, and any edge incident with $u$ has its other endpoint in $C$. Intervals are automatic for vertices of $C$ and singletons for $I$. Therefore \[ \operatorname{pw}(G)\le |C| \le n-\lceil n/4\rceil=\lfloor3n/4\rfloor. \] This self-contained bound is deliberately not represented as the best asymptotic result in the literature. Its purpose is to supply a rigorous comparison for the finite ordering method.

How expansion creates a lower bound.

Suppose, additionally, that every $S$ with $|S|\le n/2$ has at least $h|S|$ edges to its complement. Each vertex counted by $b(S)$ supports at most three such edges, so $3b(S)\ge h|S|$. Every ordering has a prefix of size $\lfloor n/2\rfloor$, yielding \[ \operatorname{pw}(G)\ge \left\lceil\frac{h\lfloor n/2\rfloor}{3}\right\rceil. \] This is conditional on an established expansion constant for the particular graph. It explains a mechanism for large pathwidth, but does not prove that graphs with any specified value of $h$ exist at every order. A spectral expansion estimate could be inserted only after all its hypotheses and constants were checked.

Executed exact calculations.

The subset recurrence was run on $K_4$, $K_{3,3}$, the three-dimensional cube, and the Petersen graph. It gives respectively \[ 3,\quad3,\quad4,\quad5. \] Each computation stores an attaining ordering. For $K_4$, any first three vertices still have a neighbour outside, so the lower bound three is immediate. For $K_{3,3}$, at a prefix of three vertices every one has a neighbour outside, whether the prefix meets one part or both. Taking one part as a vertex cover gives the matching upper bound three. The cube and Petersen values were certified by all $2^8$ and $2^{10}$ states of the recurrence, not by a heuristic ordering search.

The script and results are checks_graphs.py and results_graphs.json under _Local/Erdos_problems/UnsolvedMath/attempt_audit_2026_10_01/number_theory/. Thus the extremal function is at least four at order eight and at least five at order ten. These are lower bounds on the extremal function; the calculation does not exclude other cubic graphs at those orders having still larger pathwidth.

Remaining gap and outcome.

The ordering characterization provides an exact finite algorithm and connects the question to separator and expansion estimates. To determine the requested extremal function one needs matching universal upper bounds and graph families meeting them, or exhaustive cubic-graph enumerations for specified small orders. Neither the elementary cover bound nor four exact examples supplies this classification. Outcome: UNRESOLVED.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1422 (GRAPH-035), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 F. V. Fomin and K. Høie, Pathwidth of cubic graphs and exact algorithms, Information Processing Letters 97 $2006$, 191--196. https://doi.org/10.1016/j.ipl.2005.10.010. Bibliographic information from the supplied record.

• S3 Cubic graph overview. https://en.wikipedia.org/wiki/Cubic_graph. Bibliographic information from the supplied record.

• E1 Fedor V. Fomin, author publication list, entry for F. V. Fomin and K. Høie, Pathwidth of cubic graphs and exact algorithms, Information Processing Letters 97 $2006$, 191--196. https://fedorvf.github.io/articles/full_fvf_publications.html. Author-maintained bibliographic listing inspected 1 October 2026. The publisher DOI retrieval failed and the former Bergen technical-report URL redirected to a department page; no theorem from an unavailable full text is used as a premise in the self-contained bounds above.