A Relative of Hadwiger's Conjecture
A Relative of Hadwiger's Conjecture
复制标题
哈维格猜想的一个亲戚
DOI：
10.1137/141002177
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
P. Seymour
中科院分区：
文献类型：
--
作者：
Katherine Edwards;D. Kang;Jaehoon Kim;Sang;P. Seymour
Hadwiger猜想认为，如果简单图G没有K t+1的子图，则它的顶点集V（G）可划分为t个稳定集。这仍然是开放的，但我们证明了在相同的假设下，$V（G）$可以划分为$t$集$X_1，\ldots，X_t $，使得对于$1\le i\le t$，在$X_i$上诱导的子图的最大度至多为$t$的函数。这是尖锐的，因为如果我们要求划分成具有相同性质的$t-1$集，结论就变成假的。
Hadwiger's conjecture asserts that if a simple graph $G$ has no $K_{t+1}$ minor, then its vertex set $V(G)$ can be partitioned into $t$ stable sets. This is still open, but we prove under the same hypothesis that $V(G)$ can be partitioned into $t$ sets $X_1,\ldots,X_t$, such that for $1\le i\le t$, the subgraph induced on $X_i$ has maximum degree at most a function of $t$. This is sharp, in that the conclusion becomes false if we ask for a partition into $t-1$ sets with the same property.