TY - JOUR

T1 - Every H-decomposition of Kn has a Nearly Resolvable Alternative

AU - Alon, Noga

AU - Yuster, Raphael

N1 - Funding Information:
The authors thank Y. Caro for valuable discussions. Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva, Center for Geometry at Tel Aviv University.

PY - 2000/10

Y1 - 2000/10

N2 - Let H be a fixed graph. An H-decomposition of Kn is a coloring of the edges of Kn 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 Kn, denoted χ(L), is the minimum number t such that the color classes (i.e., the members) of L can be partitioned into t subsets L1 , . . . , Lt, 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 Kn has an H-decomposition, it also has a decomposition L satisfying χ(L) = n-1/d(1 + 0n(1)).

AB - Let H be a fixed graph. An H-decomposition of Kn is a coloring of the edges of Kn 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 Kn, denoted χ(L), is the minimum number t such that the color classes (i.e., the members) of L can be partitioned into t subsets L1 , . . . , Lt, 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 Kn has an H-decomposition, it also has a decomposition L satisfying χ(L) = n-1/d(1 + 0n(1)).

UR - http://www.scopus.com/inward/record.url?scp=0034402367&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034402367&partnerID=8YFLogxK

U2 - 10.1006/eujc.2000.0400

DO - 10.1006/eujc.2000.0400

M3 - Article

AN - SCOPUS:0034402367

VL - 21

SP - 839

EP - 845

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

IS - 7

ER -