Discussiones Mathematicae Graph Theory 33(4) (2013) 771-784
doi: 10.7151/dmgt.1710

[BIBTex] [PDF] [PS]

Almost-rainbow Edge-colorings of Some Small Subgraphs

Elliot Krop

Department of Mathematics, Clayton State University
2000 Clayton State Boulevard, Morrow, GA 30260 USA

Irina Krop

DePaul University
1 E. Jackson, Chicago, IL 60604 USA


Let f(n,p,q) be the minimum number of colors necessary to color the edges of Kn so that every Kp 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,9) ≥ 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=Kn,n, we show an n-color construction to color the edges of G so that every C4⊆ 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

2010 Mathematics Subject Classification: 05A15, 05C38, 05C55.


[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)..

Received 6 December 2012
Revised 21 September 2012
Accepted 21 September 2012