Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2212.02388 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913390872494080 |
|---|---|
| author | Dujmović, Vida Joret, Gwenaël Micek, Piotr Morin, Pat Wood, David R. |
| author_facet | Dujmović, Vida Joret, Gwenaël Micek, Piotr Morin, Pat Wood, David R. |
| contents | 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\subseteq 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 $Δ$ and treewidth $t$, then $tΔc \ge 2^{Ω(\sqrt{\log\log n})}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_02388 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure Dujmović, Vida Joret, Gwenaël Micek, Piotr Morin, Pat Wood, David R. Combinatorics 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\subseteq 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 $Δ$ and treewidth $t$, then $tΔc \ge 2^{Ω(\sqrt{\log\log n})}$. |
| title | Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2212.02388 |