Almost-Rainbow Edge-Colorings of Some Small Subgraphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 771-784
Voir la notice de l'article provenant de la source Library of Science
Let f(n, p, q) be the minimum number of colors necessary to color the edges of K_n so that every K_p is at least q-colored. We improve current bounds on these nearly “anti-Ramsey” numbers, first studied by Erdös and Gyárfás. We show that f(n, 5, 0) ≥7/4 n - 3, slightly improving the bound of Axenovich. We make small improvements on bounds of Erdös and Gyárfás by showing 5/6 n + 1 ≤ f(n,4,5) and for all even n ≢ 1(mod 3), f(n, 4, 5) ≤ n−1. For a complete bipartite graph G= K_n,n, we show an n-color construction to color the edges of G so that every C_4 ⊆ G is colored by at least three colors. This improves the best known upper bound of Axenovich, Füredi, and Mubayi.
Keywords:
Ramsey theory, generalized Ramsey theory, rainbow-coloring, edge-coloring, Erdös problem
@article{DMGT_2013_33_4_a11,
author = {Krop, Elliot and Krop, Irina},
title = {Almost-Rainbow {Edge-Colorings} of {Some} {Small} {Subgraphs}},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {771--784},
publisher = {mathdoc},
volume = {33},
number = {4},
year = {2013},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a11/}
}
Krop, Elliot; Krop, Irina. Almost-Rainbow Edge-Colorings of Some Small Subgraphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 771-784. http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a11/