Proof of a tiling conjecture of Komlós
Proof of a tiling conjecture of Komlós
复制标题
Komlós 平铺猜想的证明
DOI：
10.1002/rsa.10091
复制
发表时间：
2003
影响因子：
1
通讯作者：
Yi Zhao
中科院分区：
文献类型：
--
作者：
A. Shokoufandeh;Yi Zhao
Komlós的一个猜想表明，对于每一个图H，存在一个常数K，使得如果G是任何最小度至少为(1−(1/χcr(H)) n的n顶点图，其中χcr(H)表示H的临界色数，则G包含一个H匹配，该匹配覆盖G的所有顶点，但不超过K个顶点。本文证明了该猜想对所有足够大的n值都成立。©2003 Wiley期刊公司。随机结构。Alg。科学通报，23:180-205,2003
A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n‐vertex graph of minimum degree at least (1 − (1/χcr(H)))n, where χcr(H) denotes the critical chromatic number of H, then G contains an H‐matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180–205, 2003