Surveys in Mathematics and its Applications

ISSN 1842-6298 (electronic), 1843-7265 (print)
 Volume 13 (2018), 131 -- 145

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

WEAKENED GALLAI-RAMSEY NUMBERS

Gabrielle Beam and Mark Budden

Abstract. In the Ramsey theory of graphs, one seeks to determine the value of the Ramsey number rt(n), defined to be the least natural number p such that every coloring of the edges of Kp using t colors results in a monochromatic copy of Kn in some color. In this paper, we demonstrate the standard techniques used for finding bounds for Ramsey numbers by combining two standard generalizations of rt(n). First, we restrict our attention to Gallai colorings: those that avoid rainbow triangles. Within this setting, we then focus on finding subgraphs isomorphic to Kn that are spanned by edges using at most s ≤ t-1 colors. The resulting generalization of rt(n) is called a weakened Gallai-Ramsey number, denoted grst(n). As such, we determine several explicit small values and prove a few general properties of such numbers.

2010 Mathematics Subject Classification: Primary 05C55; 05C15; Secondary 05C35; 05D10.
Keywords: Gallai colorings, lexicographic product, Ramsey number.

Full text

References

  1. M. Budden, M. Stender, and Y. Zhang, Weakened Ramsey numbers and their hypergraph analogues, INTEGERS 17 (2017), #A23. MR3667572.  

  2. F. Chung and R. Graham, Edge-colored complete graphs with precisely colored subgraphs, Combinatorica 3 (1983), 315-324. MR0729784(85g:05107). Zbl 0529.05041.

  3. K. Chung, M. Chung, and C. Liu, A generalization of Ramsey theory for graphs - with stars and complete graphs as forbidden subgraphs, Congr. Numer. 19 (1977), 155-161. MR0485535(58 #5365). Zbl 0435.05046.

  4. K. Chung and C. Liu, A generalization of Ramsey theory for graphs, Discrete Math. 21 (1978), 117-127. MR0523059(80c:05100).

  5. P. Erd\Hos, M. Simonovits, and V. T. Sós, Anti-Ramsey theorems, Coll. Math. Soc. J. Bolyai 10 (1973), 633-643. MR0379258(52 #164).

  6. R. Faudree, R. Gould, M. Jacobson, and C. Magnant, Ramsey numbers in rainbow triangle free colorings, Australas. J. Combin. 46 (2010), 269-284. MR2598711(2011d:05239). Zbl 1196.05052.

  7. J. Fox, A. Grinshpun, and J. Pach, The Erd\Hos-Hajnal conjecture for rainbow triangles, J. Combin. Theory Ser. B 111 (2015), 75-125. MR3315601. Zbl 1307.05069.

  8. S. Fujita, C. Magnant, and K. Ozeki, Rainbow generalizations of Ramsey theory - a dynamic survey, Theory and Applications of Graphs 0(1). (2014), Article 1. MR2606615(2011i:05148). Zbl 1231.05178.

  9. S. Fujita, B. Ning, C. Xu, and S. Zhang, On sufficient conditions for rainbow cycles in edge-colored graphs, preprint.

  10. T. Gallai, Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25-66. MR0221974(36 #5026). Zbl 0153.26002.

  11. R. Greenwood and A. Gleason, Combinatorial relations and chromatic graphs, Canadian Journ. Math. 7 (1955), 1-7. MR0067467(16,733g). Zbl 0064.17901.

  12. A. Gyárfás and G. Simonyi, Edge colorings of complete graphs without tricolored triangles, J. Graph Theory 46(3) (2004), 211-216. MR2063371(2005a:05086). Zbl 1041.05028.

  13. H. Harborth and M. Möller, Weakened Ramsey numbers, Discrete Appl. Math. 95 (1999), 279-284. MR1708843(2000d:05079). Zbl 0932.05062.

  14. M. Jacobson, On a generalization of Ramsey theory, Discrete Math. 38 (1982), 191-195. MR0676536(84g:05105). Zbl 0476.05056.

  15. S. Radziszowski, Small Ramsey numbers - revision 15, Electron. J. Combin. DS1.15 (2017), 1-104. MR1670625(99k:05117). Zbl 0953.05048.

  16. F. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1929), 264-286. MR1576401. Zbl 55.0032.04.



Gabrielle Beam
Department of Mathematics and Computer Science
Western Carolina University
Cullowhee, NC, USA 28723
e-mail: gibeam1@catamount.wcu.edu

Mark Budden
Department of Mathematics and Computer Science
Western Carolina University
Cullowhee, NC, USA 28723
e-mail: mrbudden@email.wcu.edu
https://agora.cs.wcu.edu/\simmbudden/

http://www.utgjiu.ro/math/sma