Partitioning 3-colored complete graphs into three monochromatic cycles
The electronic journal of combinatorics, Tome 18 (2011) no. 1
We show in this paper that in every $3$-coloring of the edges of $K^n$ all but $o(n)$ of its vertices can be partitioned into three monochromatic cycles. From this, using our earlier results, actually it follows that we can partition all the vertices into at most 17 monochromatic cycles, improving the best known bounds. If the colors of the three monochromatic cycles must be different then one can cover $({3\over 4}-o(1))n$ vertices and this is close to best possible.
@article{10_37236_540,
author = {Andr\'as Gy\'arf\'as and Mikl\'os Ruszink\'o and G\'abor N. S\'ark\"ozy and Endre Szemer\'edi},
title = {Partitioning 3-colored complete graphs into three monochromatic cycles},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/540},
zbl = {1217.05185},
url = {http://geodesic.mathdoc.fr/articles/10.37236/540/}
}
TY - JOUR AU - András Gyárfás AU - Miklós Ruszinkó AU - Gábor N. Sárközy AU - Endre Szemerédi TI - Partitioning 3-colored complete graphs into three monochromatic cycles JO - The electronic journal of combinatorics PY - 2011 VL - 18 IS - 1 UR - http://geodesic.mathdoc.fr/articles/10.37236/540/ DO - 10.37236/540 ID - 10_37236_540 ER -
%0 Journal Article %A András Gyárfás %A Miklós Ruszinkó %A Gábor N. Sárközy %A Endre Szemerédi %T Partitioning 3-colored complete graphs into three monochromatic cycles %J The electronic journal of combinatorics %D 2011 %V 18 %N 1 %U http://geodesic.mathdoc.fr/articles/10.37236/540/ %R 10.37236/540 %F 10_37236_540
András Gyárfás; Miklós Ruszinkó; Gábor N. Sárközy; Endre Szemerédi. Partitioning 3-colored complete graphs into three monochromatic cycles. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/540
Cité par Sources :