Marc Distel ; Kevin Hendrey ; Nikolai Karol ; David R. Wood ; Jung Hon Yip - Treewidth 2 in the Planar Graph Product Structure Theorem

dmtcs:14785 - Discrete Mathematics & Theoretical Computer Science, March 17, 2025, vol. 27:2 - https://doi.org/10.46298/dmtcs.14785
Treewidth 2 in the Planar Graph Product Structure TheoremArticle

Authors: Marc Distel ; Kevin Hendrey ; Nikolai Karol ; David R. Wood ; Jung Hon Yip

    We prove that every planar graph is contained in $H_1\boxtimes H_2\boxtimes K_2$ for some graphs $H_1$ and $H_2$ both with treewidth 2. This resolves a question of Liu, Norin and Wood [arXiv:2410.20333]. We also show this result is best possible: for any $c \in \mathbb{N}$, there is a planar graph $G$ such that for any tree $T$ and graph $H$ with $\text{tw}(H) \leqslant 2$, $G$ is not contained in $H \boxtimes T \boxtimes K_c$.


    Volume: vol. 27:2
    Section: Graph Theory
    Published on: March 17, 2025
    Accepted on: March 11, 2025
    Submitted on: November 18, 2024
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics

    Consultation statistics

    This page has been seen 132 times.
    This article's PDF has been downloaded 619 times.