论文标题
有限的平面图没有界度的产品结构
Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure
论文作者
论文摘要
产品结构定理是最新结果的集合，这些结果已用于解决平面图和相关图类别上的许多长期开放问题。一个特别有用的版本指出，每个平面图$ g $都包含在$ 3 $ -tree $ h $，路径$ p $的强产品中，而$ 3 $ -CRECLE $ k_3 $;写为$ g \ subseteq h \ boxtimes p \ boxtimes k_3 $。许多研究人员询问是否可以加强此定理，以便可以在$ h $中获得最高学位的最高学位。我们表明，不可能加强这种加强。具体而言，我们描述了一个无限家庭的$ \ nathcal {g} $最高度$ 5 $的平面图$ 5 $，这样，如果$ n $ vertex成员$ g $ $ \ nathcal {g} $是同构的，则是$ h \ boxtimes p \ boxtimes p \ boxtimes k_c $ path a Gath and a Graph and a Graph and a Graph and a Graph and a Graph and的图形。 $ t $，然后$tδc\ ge 2^{ω（\ sqrt {\ log \ log n}）} $。
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})}$.
