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 H1H2K2 for some graphs H1 and H2 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 cN, there is a planar graph G such that for any tree T and graph H with tw(H)2, G is not contained in HTKc.


    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 77 times.
    This article's PDF has been downloaded 36 times.