PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 4 | 771-784
Tytuł artykułu

Almost-Rainbow Edge-Colorings of Some Small Subgraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
33
Numer
4
Strony
771-784
Opis fizyczny
Daty
wydano
2013-09-01
online
2013-10-15
Twórcy
autor
  • Department of Mathematics, Clayton State University 2000 Clayton State Boulevard, Morrow, GA 30260 USA, ElliotKrop@clayton.edu
autor
Bibliografia
  • [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]
  • [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]
  • [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]
  • [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]
  • [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]
  • [9] D. Mubayi, Edge-coloring cliques with three colors on all four cliques, Combinatorica 18 (1998) 293-296. doi:10.1007/PL00009822[Crossref]
  • [10] R. Wilson, Graph Theory, Fourth Edition (Prentice Hall, Pearson Education Limited, 1996).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1710
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.