## Abstract

We solve four similar problems: for every fixed s and large n, we describe all values of n_{1}, …, n_{s} such that for every 2-edge-coloring of the complete s-partite graph K_{n1},…,n_{s} there exists a monochromatic (i) cycle C_{2n} with 2n vertices, (ii) cycle C_{≥2n} with at least 2n vertices, (iii) path P_{2n} with 2n vertices, and (iv) path P_{2n+1} with 2n + 1 vertices. This implies a generalization for large n of the conjecture by Gyárfás, Ruszinkó, Sárközy and Szemerédi that for every 2-edge-coloring of the complete 3-partite graph K_{n,n,n} there is a monochromatic path P_{2n+1} . An important tool is our recent stability theorem on monochromatic connected matchings.

Original language | English |
---|---|

Pages (from-to) | 55-100 |

Number of pages | 46 |

Journal | Moscow Journal of Combinatorics and Number Theory |

Volume | 9 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2020 |

Externally published | Yes |

## Keywords

- Paths and cycles
- Ramsey number
- Regularity Lemma