Article in press
Authors:
Title:
Gallai-Ramsey numbers for rainbow trees and monochromatic complete bipartite graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-11-08 , Revised: 2024-07-06 , Accepted: 2024-07-13 , Available online: 2024-08-30 , https://doi.org/10.7151/dmgt.2555
Abstract:
Given two non-empty graphs $G,H$ and a positive integer $k$, the Gallai-Ramsey
number $\textrm{gr}_k(G:H)$ is defined as the minimum positive integer $N$ such
that for all $n\geq N$, every $k$-edge-colored $K_n$ contains either a rainbow
subgraph $G$ or a monochromatic subgraph $H$. In this paper, we get some exact
values or bounds of $\textrm{gr}_k(K_{1,3}:H)$, $\textrm{gr}_k(P_5:H)$, and
$\textrm{gr}_k(P_4^{+}:H)$ for $k\geq 3$, where $H$ is a complete bipartite graph.
Keywords:
Ramsey theory, Gallai-Ramsey number, complete bipartite graph
References:
- R. Bass, C. Magnant, K. Ozeki and B. Pyron, Characterizations of edge-colorings of complete graphs that forbid certain rainbow subgraphs (2022), manuscript.
- J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer, London, 2008).
https://doi.org/10.1007/978-1-84628-970-5 - S.A. Burr, Diagonal Ramsey numbers for small graphs, J. Graph Theory 7 (1983) 57–69.
https://doi.org/10.1002/jgt.3190070108 - K. Cameron and J. Edmonds, Lambda composition, J. Graph Theory 26 (1997) 9–16.
https://doi.org/10.1002/(SICI)1097-0118(199709)26:1<9::AID-JGT2>3.0.CO;2-N - R.J. Faudree, R. Gould, M. Jacobson and C. Magnant, Ramsey numbers in rainbow triangle free colorings, Australas. J. Combin. 46 (2010) 269–284.
- S. Fujita and C. Magnant, Extensions of Gallai-Ramsey results, J. Graph Theory 70 (2012) 404–426.
https://doi.org/10.1002/jgt.20622 - T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hung. 18 (1967) 25–66.
https://doi.org/10.1007/BF02020961 - A. Gyárfás, J. Lehel, R.H. Schelp and Zs. Tuza, Ramsey numbers for local colorings, Graphs Combin. 3 (1987) 267–277.
https://doi.org/10.1007/BF01788549 - A. Gyárfás and G. Simony, Edge colorings of complete graphs without tricolored triangles, J. Graph Theory 46 (2004) 211–216.
https://doi.org/10.1002/jgt.20001 - H. Harborth and I. Mengersen, The Ramsey number of $K_{3,3}$, in: Combinatorics, Graph Theory, and Applications Vol. 2, Y. Alavi, G. Chartrand, O.R. Oellermann and A.J. Schwenk (Ed(s)), (John Wiley & Sons 1991) 639–644.
- X.-H. Li, P. Besse, C. Magnant, L.-G. Wang and N. Watts, Gallai-Ramsey numbers for rainbow paths, Graphs Combin. 36 (2020) 1163–1175.
https://doi.org/10.1007/s00373-020-02175-8 - X.-H. Li and L.-G. Wang, Monochromatic stars in rainbow $K_3$-free and $S_3^+$-free colorings, Discrete Math. 343 (2020) 112131.
https://doi.org/10.1016/j.disc.2020.112131 - X.-H. Li, L.-G. Wang and X.-X. Liu, Complete graphs and complete bipartite graphs without rainbow path, Discrete Math. 342 (2019) 2116–2126.
https://doi.org/10.1016/j.disc.2019.04.010 - C. Magnant and P.S. Nowbandegani, Topics in Gallai-Ramsey Theory (Springer Cham, 2020).
https://doi.org/10.1007/978-3-030-48897-0 - S. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2021) DS1.
https://doi.org/10.37236/21 - F.P. Ramsey, On a problem of formal logic, Proc. Lond. Math. Soc. (2) 30 (1930) 264–286.
https://doi.org/10.1112/plms/s2-30.1.264 - J.C. Schlage-Puchta and P. Wagner, Complete graphs with no rainbow tree, J. Graph Theory 93 (2020) 157–167.
https://doi.org/10.1002/jgt.22479 - A. Thomason and P. Wagner, Complete graphs with no rainbow path, J. Graph Theory 54 (2007) 261–266.
https://doi.org/10.1002/jgt.20207 - J.-N. Zhou, Z.-H. Li, Y.-P. Mao and M.-Q. Wei, Ramsey and Gallai-Ramsey numbers for the union of paths and stars, Discrete Appl. Math. 325 (2023) 297–308.
https://doi.org/10.1016/j.dam.2022.10.022 - J.-Y. Zou, Z. Wang, H.-J. Lai and Y.-P. Mao, Gallai-Ramsey numbers involving a rainbow $4$-path, Graphs Combin. 39 (2023) 54.
https://doi.org/10.1007/s00373-023-02648-6
Close