Geodesic
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/}
}
TY  - JOUR
AU  - Krop, Elliot
AU  - Krop, Irina
TI  - Almost-Rainbow Edge-Colorings of Some Small Subgraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 771
EP  - 784
VL  - 33
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a11/
LA  - en
ID  - DMGT_2013_33_4_a11
ER  - 
%0 Journal Article
%A Krop, Elliot
%A Krop, Irina
%T Almost-Rainbow Edge-Colorings of Some Small Subgraphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 771-784
%V 33
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a11/
%G en
%F 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/

[1] M. Axenovich, A generalized Ramsey problem, Discrete Math. 222 (2000) 247-249. doi:10.1016/S0012-365X(00)00052-2

[2] M. Axenovich, Z. Füredi and D. Mubayi, On generalized Ramsey theory: the bipartite case, J. Combin. Theory (B) 79 (2000) 66-86. doi:10.1006/jctb.1999.1948

[3] R. Diestel, Graph Theory, Third Edition (Springer-Verlag, Heidelberg, Graduate Texts in Mathematics, Volume 173, 2005).

[4] P. Erdös, Solved and unsolved problems in combinatorics and combinatorial number theory, Congr. Numer. 32 (1981) 49-62.

[5] P. Erdös and A. Gyárfás, A variant of the classical Ramsey problem, Combinatorica 17 (1997) 459-467. doi:10.1007/BF01195000

[6] J. Fox and B. Sudakov, Ramsey-type problem for an almost monochromatic K4, SIAM J. Discrete Math. 23 (2008) 155-162. doi:10.1137/070706628

[7] S. Fujita, C. Magnant and K. Ozeki, Rainbow generalizations of Ramsey theory: A survey, Graphs Combin. 26 (2010) 1-30. doi:10.1007/s00373-010-0891-3

[8] A. Kostochka and D. Mubayi, When is an almost monochromatic K4 guaranteed?, Combin. Probab. Comput. 17 (2008) 823-830. doi:10.1017/S0963548308009413

[9] D. Mubayi, Edge-coloring cliques with three colors on all four cliques, Combinatorica 18 (1998) 293-296. doi:10.1007/PL00009822

[10] R. Wilson, Graph Theory, Fourth Edition (Prentice Hall, Pearson Education Limited, 1996).