Back to Search
Start Over
Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure
Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure
- Publication Year :
- 2022
- Publisher :
- arXiv, 2022.
-
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 $G\subsetcong H\boxtimes P\boxtimes K_3$. 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 $\mathcal{G}$ of planar graphs of maximum degree $5$ such that, if an $n$-vertex member $G$ of $\mathcal{G}$ is isomorphic to a subgraph of $H\boxtimes P\boxtimes K_c$ where $P$ is a path and $H$ is a graph of maximum degree $\Delta$ and treewidth $t$, then $t\Delta c \ge 2^{\Omega(\sqrt{\log\log n})}$.<br />Comment: 14 pages, 4 figures
- Subjects :
- FOS: Mathematics
Mathematics - Combinatorics
Combinatorics (math.CO)
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....87d7b769c19337efe8813336b5a70635
- Full Text :
- https://doi.org/10.48550/arxiv.2212.02388