Monochromatic Hamiltonian Berge-cycles in colored complete uniform hypergraphs

  • Gyárfás, András
  • Lehel, Jenő
  • Sárközy, Gábor N.
  • Schelp, R.H.
ORKG logo View in ORKG
Publication date
March 2008
Publisher
Elsevier Inc.

Abstract

AbstractWe conjecture that for any fixed r and sufficiently large n, there is a monochromatic Hamiltonian Berge-cycle in every (r−1)-coloring of the edges of Kn(r), the complete r-uniform hypergraph on n vertices. We prove the conjecture for r=3,n⩾5 and its asymptotic version for r=4. For general r we prove weaker forms of the conjecture: there is a Hamiltonian Berge-cycle in ⌊(r−1)/2⌋-colorings of Kn(r) for large n; and a Berge-cycle of order (1−o(1))n in (r−⌊log2r⌋)-colorings of Kn(r). The asymptotic results are obtained with the Regularity Lemma via the existence of monochromatic connected almost perfect matchings in the multicolored shadow graph induced by the coloring of Kn(r)

Extracted data

We use cookies to provide a better user experience.