Every H-decomposition of Kn has a Nearly Resolvable Alternative

Noga Alon, Raphael Yuster

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

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)).

Original languageEnglish (US)
Pages (from-to)839-845
Number of pages7
JournalEuropean Journal of Combinatorics
Volume21
Issue number7
DOIs
StatePublished - Oct 2000
Externally publishedYes

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