Cover $k$-Uniform Hypergraphs by Monochromatic Loose Paths

  • Changhong Lu
  • Rui Mao
  • Bing Wang
  • Ping Zhang
Keywords: Hypergraph, Monochromatic loose path

Abstract

A conjecture of Gyárfás and Sárközy says that in every $2$-coloring of the edges of the complete $k$-uniform hypergraph $\mathcal{K}_n^k$, there are two disjoint monochromatic loose paths of distinct colors such that they cover all but at most $k-2$ vertices. Recently, the authors affirmed the conjecture. In the note we show that for every $2$-coloring of $\mathcal{K}_n^k$, one can find two monochromatic paths of distinct colors to cover all vertices of $\mathcal{K}_n^k$ such that they share at most $k-2$ vertices. Omidi and Shahsiah conjectured that $R(\mathcal{P}_t^k,\mathcal{P}_t^k) =t(k-1)+\lfloor \frac{t+1}{2}\rfloor$ holds for $k\ge 3$ and they affirmed the conjecture for $k=3$ or $k\ge 8$. We show that if the conjecture is true, then $k-2$ is best possible for our result.

Published
2017-10-20
Article Number
P4.23