# Almost-Rainbow Edge-Colorings of Some Small Subgraphs

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 4, page 771-784
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topElliot Krop, and Irina Krop. "Almost-Rainbow Edge-Colorings of Some Small Subgraphs." Discussiones Mathematicae Graph Theory 33.4 (2013): 771-784. <http://eudml.org/doc/268325>.

@article{ElliotKrop2013,

abstract = {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 [...] , slightly improving the bound of Axenovich. We make small improvements on bounds of Erdös and Gyárfás by showing [...] 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.},

author = {Elliot Krop, Irina Krop},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {Ramsey theory; generalized Ramsey theory; rainbow-coloring; edge-coloring; Erdös problem; Erdős problem},

language = {eng},

number = {4},

pages = {771-784},

title = {Almost-Rainbow Edge-Colorings of Some Small Subgraphs},

url = {http://eudml.org/doc/268325},

volume = {33},

year = {2013},

}

TY - JOUR

AU - Elliot Krop

AU - Irina Krop

TI - Almost-Rainbow Edge-Colorings of Some Small Subgraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 4

SP - 771

EP - 784

AB - 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 [...] , slightly improving the bound of Axenovich. We make small improvements on bounds of Erdös and Gyárfás by showing [...] 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.

LA - eng

KW - Ramsey theory; generalized Ramsey theory; rainbow-coloring; edge-coloring; Erdös problem; Erdős problem

UR - http://eudml.org/doc/268325

ER -

## References

top- [1] M. Axenovich, A generalized Ramsey problem, Discrete Math. 222 (2000) 247-249. doi:10.1016/S0012-365X(00)00052-2[Crossref]
- [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[Crossref] Zbl1023.05101
- [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[Crossref] Zbl0910.05034
- [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[Crossref][WoS] Zbl1190.05085
- [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[Crossref] Zbl1231.05178
- [8] A. Kostochka and D. Mubayi, When is an almost monochromatic K4 guaranteed?, Combin. Probab. Comput. 17 (2008) 823-830. doi:10.1017/S0963548308009413[WoS][Crossref] Zbl1180.05071
- [9] D. Mubayi, Edge-coloring cliques with three colors on all four cliques, Combinatorica 18 (1998) 293-296. doi:10.1007/PL00009822[Crossref] Zbl0910.05035
- [10] R. Wilson, Graph Theory, Fourth Edition (Prentice Hall, Pearson Education Limited, 1996).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.