期刊
SIAM JOURNAL ON DISCRETE MATHEMATICS
卷 29, 期 4, 页码 2385-2388出版社
SIAM PUBLICATIONS
DOI: 10.1137/141002177
关键词
improper coloring; minor; Hadwiger's conjecture
资金
- NSERC PGS-D3 fellowship
- Gordon Wu fellowship
- ONR [N00014-10-1-0680]
- NSF [DMS-1265563]
- National Research Foundation of Korea (NRF) - Ministry of Science, ICT, and Future Planning [2011-0011653]
- Division Of Mathematical Sciences
- Direct For Mathematical & Physical Scien [1265563] Funding Source: National Science Foundation
- National Research Foundation of Korea [2011-0011653] Funding Source: Korea Institute of Science & Technology Information (KISTI), National Science & Technology Information Service (NTIS)
Hadwiger's conjecture asserts that if a simple graph G has no Kt+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, ..., X-t, such that for 1 <= i <= 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据