Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure
arxiv(2022)
摘要
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⊆ H⊠ P⊠ 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 𝒢 of planar graphs of maximum degree 5 such
that, if an n-vertex member G of 𝒢 is isomorphic to a subgraph
of H⊠ P⊠ K_c where P is a path and H is a graph of
maximum degree Δ and treewidth t, then tΔ c ≥
2^Ω(√(loglog n)).
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要