The minimum degree threshold for perfect graph packings
The minimum degree threshold for perfect graph packings
复制标题
DOI：
10.1007/s00493-009-2254-3
复制
发表时间：
2006-03
期刊：
影响因子：
1.1
通讯作者：
D. Kühn;Deryk Osthus
中科院分区：
文献类型：
--
作者：
D. Kühn;Deryk Osthus
任何图形都可以。我们在一个加性常数范围内确定图的最小度，以确保图具有完美填充（也称为h因子）。更精确地说，设δ(H,n)表示最小的整数，使得每一个有序度可被|H|整除且δ(G)≥k的图都包含一个完全填充。我们证明了这一点。χ*(H)的值取决于hand的最优着色中颜色类的相对大小，χ(H)−1<χ*(H)≤χ(H)。
LetHbe any graph. We determine up to an additive constant the minimum degree of a graphGwhich ensures thatGhas a perfectH-packing (also called anH-factor). More precisely, letδ(H,n) denote the smallest integerksuch that every graphGwhose ordernis divisible by |H| and withδ(G)≥kcontains a perfectH-packing. We show that.The value ofχ*(H) depends on the relative sizes of the colour classes in the optimal colourings ofHand satisfiesχ(H)−1<χ*(H)≤χ(H).