### Abstract

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 + 0_{n}(1)).

Original language | English (US) |
---|---|

Pages (from-to) | 839-845 |

Number of pages | 7 |

Journal | European Journal of Combinatorics |

Volume | 21 |

Issue number | 7 |

DOIs | |

State | Published - Oct 2000 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'Every H-decomposition of K<sub>n</sub> has a Nearly Resolvable Alternative'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Yuster, R. (2000). Every H-decomposition of K

_{n}has a Nearly Resolvable Alternative.*European Journal of Combinatorics*,*21*(7), 839-845. https://doi.org/10.1006/eujc.2000.0400