Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure

DOI10.37236/11712MaRDI QIDQ6419593zbMATH OpenFDO

Authors Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, David R. Wood

Publication date 5 December 2022

Full work available at URL https://doi.org/10.37236/11712

Abstract: Product structure theorems are a collection of recent results that have been used to resolve a number of longstanding open problems on planar graphs and related graph classes. One particularly useful version states that every planar graph $G$ is contained in the strong product of a $3$-tree $H$, a path $P$, and a $3$-cycle $K_3$; written as $$. A number of researchers have asked if this theorem can be strengthened so that the maximum degree in $H$ can be bounded by a function of the maximum degree in $G$. We show that no such strengthening is possible. Specifically, we describe an infinite family $mathcalG$ of planar graphs of maximum degree $5$ such that, if an $n$-vertex member $G$ of $mathcalG$ is isomorphic to a subgraph of $$ where $P$ is a path and $H$ is a graph of maximum degree $Delta$ and treewidth $t$, then $tDeltacge{2}^{Omega(sqrtloglogn)}$.

This page was built for publication: Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure

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