Equivalence between pathbreadth and strong pathbreadth

DOI10.1016/J.DAM.2019.02.009MaRDI QIDQ2416435zbMATH OpenOpenAlexFDO

Authors Guillaume Ducoffe, Arne Leitert

Publication date 23 May 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.06041

zbMATH Keywords

path decompositionAT-free graphsstrong pathbreadthpathbreadthdominating pair

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We say that a given graph $G=(V,E)$ has emph{pathbreadth} at most $ho$, denoted $pb(G)leqho$, if there exists a Roberston and Seymour's path decomposition where every bag is contained in the $ho$-neighbourhood of some vertex. Similarly, we say that $G$ has emph{strong pathbreadth} at most $ho$, denoted $spb(G)leqho$, if there exists a Roberston and Seymour's path decomposition where every bag is the complete $ho$-neighbourhood of some vertex. It is straightforward that $pb(G)leqspb(G)$ for any graph $G$. Inspired from a close conjecture in [Leitert and Dragan, COCOA'16], we prove in this note that $spb(G)leq4cdotpb(G)$.

Recommendations

• A short note on the complexity of computing strong pathbreadth
• On strong tree-breadth
• Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs
• On the path-width of planar graphs
• On the complexity of computing treebreadth

Cites work

• A short note on the complexity of computing strong pathbreadth
• Algorithms and Computation
• Asteroidal Triple-Free Graphs
• Graph theory
• Line-distortion, bandwidth and path-length of a graph
• On strong tree-breadth
• On the complexity of computing treebreadth

Cited in

(1)

• On strong tree-breadth

This page was built for publication: Equivalence between pathbreadth and strong pathbreadth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2416435)