EveryH-decomposition ofKnhas a Nearly Resolvable Alternative
✍ Scribed by Noga Alon; Raphael Yuster
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 96 KB
- Volume
- 21
- Category
- Article
- ISSN
- 0195-6698
No coin nor oath required. For personal study only.
✦ Synopsis
Let H be a fixed graph. An H -decomposition of K n is a coloring of the edges of K n such that every color class forms a copy of H . Each copy is called a member of the decomposition. The resolution number of an H -decomposition L of K n , denoted χ (L), is the minimum number t such that the color classes (i.e., the members) of L can be partitioned into t subsets L 1 , . . . , L t , where any two members belonging to the same subset are vertex-disjoint. A trivial lower bound is χ (L) ≥ n-1 d where d is the average degree of H . We prove that whenever K n has an H -decomposition, it also has a decomposition L satisfying χ(L) = n-1 d (1 + o n (1)).