Cover $k$-Uniform Hypergraphs by Monochromatic Loose Paths

Changhong Lu, Rui Mao, Bing Wang, Ping Zhang

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.


Keywords


Hypergraph; Monochromatic loose path

Full Text:

PDF