科研速览 · Science Skim继续刷下去 · Keep skimming →
◇ arXiv2026-08-14· math.CO

Product structure of graphs excluding a topological minor

Jędrzej Hodor, Hoang La, Piotr Micek, Clément Rambaud

原始摘要(英文原文)· Original abstract
We prove that, for all positive integers $h$ and $t$ and every graph $X$ with $\mathrm{td}(X) \leq h$, there exists a positive integer $c(X,t)$ such that every graph $G$ with $\mathrm{tw}(G) < t$ that excludes $X$ as a topological minor is isomorphic to a subgraph of $H \boxtimes K_{c(X,t)}$ for some graph $H$ with $\mathrm{tw}(H) < 2^{h+1}-1$. This extends a result by Ding and Oporowski (Journal of Graph Theory; 1995), which states that for all positive integers $Δ$ and $t$, here exists a positive integer $f(Δ,t)$ such that every graph $G$ with $\mathrm{tw}(G)<t$ and $Δ(G)\leqΔ$ is isomorphic to a subgraph of $T \boxtimes K_{f(Δ,t)}$ for some tree $T$.
读原文 · Read the paper ↗

AI 追问PRO

登录后使用 AI 追问

讨论区

登录后参与讨论

相关论文 · Related

Product structure of graphs excluding a topological minor — 科研速览 Science Skim