The proper pathwidth of a graph.
The proper pathwidth $\operatorname{ppw}(G)$ was introduced in [1] as the minimum width of a proper-path-decomposition. Barioli et al. [2] showed that if $G$ has at least one edge, then $\operatorname{ppw}(G)$ is the minimum $k$ for which $G$ is a minor of the Cartesian product $K_k \square P$ of a complete graph on $k$ vertices with a path; and further that $\operatorname{ppw}(G)$ is the minor monotone floor $\lfloor \operatorname{Z} \rfloor(G) := \min\{\operatorname{Z}(H) \mid G \preceq H\}$ of the zero forcing number $\operatorname{Z}(G)$. It can be shown [3, Corollary 9.130] that only the spanning supergraphs need to be considered for $H$ in this definition, i.e. $\lfloor \operatorname{Z} \rfloor(G) = \min\{\operatorname{Z}(H) \mid G \le H,\; V(H) = V(G)\}$.
The minimum degree $\delta$, treewidth $\operatorname{tw}$, and pathwidth $\operatorname{pw}$ satisfy
$$\delta \le \operatorname{tw} \le \operatorname{pw} \le \operatorname{ppw} = \lfloor \operatorname{Z} \rfloor \le \operatorname{pw} + 1.$$
Note that [4] uses a different notion of proper pathwidth, which is equal to bandwidth.

[1] Takahashi, A., Ueno, S., Kajitani, Y. Minimal acyclic forbidden minors for the family of graphs with bounded path-width MathSciNet:1273610
[2] Barioli, F., Barrett, W., Fallat, S. M., Hall, H. T., Hogben, L., Shader, B., van den Driessche, P., van der Holst, H. Parameters related to tree-width, zero forcing, and maximum nullity of a graph MathSciNet:3010007
[3] Hogben, L., Lin, J. C.-H., Shader, B. L. Inverse problems and zero forcing for graphs MathSciNet:4478249
[4] Kaplan, H., Shamir, R. Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques MathSciNet:1390027

Jan 19, 2025 at 20:34 by Lennard Hofmann

Jan 19, 2025 at 20:34 by Lennard Hofmann