Equivalence between pathbreadth and strong pathbreadth
classification
💻 cs.CC
cs.DS
keywords
pathbreadthdecompositiondenotedempheveryexistsgraphneighbourhood
read the original abstract
We say that a given graph $G = (V, E)$ has \emph{pathbreadth} at most $\rho$, denoted $\pb(G) \leq \rho$, if there exists a Roberston and Seymour's path decomposition where every bag is contained in the $\rho$-neighbourhood of some vertex. Similarly, we say that $G$ has \emph{strong pathbreadth} at most $\rho$, denoted $\spb(G) \leq \rho$, if there exists a Roberston and Seymour's path decomposition where every bag is the complete $\rho$-neighbourhood of some vertex. It is straightforward that $\pb(G) \leq \spb(G)$ for any graph $G$. Inspired from a close conjecture in [Leitert and Dragan, COCOA'16], we prove in this note that $\spb(G) \leq 4 \cdot \pb(G)$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.