Abstract
The Gallai–Ramsey number \(gr_{k}(K_{3}: H_{1}, H_{2}, \cdots , H_{k})\) is the smallest integer n such that every k-edge-colored \(K_{n}\) contains either a rainbow \(K_3\) or a monochromatic \(H_{i}\) in color i for some \(i\in [k]\). We define the star-critical Gallai–Ramsey number \(gr_{k}^{*}(K_3: H_{1}, H_{2}, \cdots , H_{k})\) as the smallest integer s such that every k-edge-colored \(K_{n}-K_{1, n-1-s}\) contains either a rainbow \(K_3\) or a monochromatic \(H_{i}\) in color i for some \(i\in [k]\). When \(H=H_{1}=\cdots =H_{k}\), we simply denote \(gr_{k}^{*}(K_{3}: H_{1}, H_{2}, \cdots , H_{k})\) by \(gr_{k}^{*}(K_{3}: H)\). We determine the star-critical Gallai–Ramsey numbers for complete graphs and some small graphs. Furthermore, we show that \(gr_{k}^{*}(K_3: H)\) is exponential in k if H is not bipartite, linear in k if H is bipartite but not a star and constant (not depending on k) if H is a star.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Cameron, K., Edmonds, J.: Lambda composition. J. Graph Theory 26(1), 9–16 (1997)
Faudree, R.J., Gould, R.J., Jacobson, M.S., Magnant, C.: Ramsey numbers in rainbow triangle free colorings. Australas. J. Combin. 46, 269–284 (2010)
Fujita, S., Magnant, C., Ozeki, K.: Rainbow generalizations of Ramsey theory—a dynamic survey. Theor. Appl. Graphs (2014). https://doi.org/10.20429/tag.2014.000101
Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar. 18, 25–66 (1967)
Gyárfás, A., Simonyi, G.: Edge colorings of complete graphs without tricolored triangles. J. Graph Theory 46(3), 211–216 (2004)
Gyárfás, A., Sárközy, G., Sebő, A., Selkow, S.: Ramsey-type results for Gallai-colorings. J. Graph Theory 64, 233–243 (2010)
Hook, J.: The classification of critical graphs and star-critical Ramsey numbers. Lehigh University, Ph.D. thesis (2010)
Hook, J., Isaak, G.: Star-critical Ramsey numbers. Discrete Appl. Math. 159, 328–334 (2011)
Magnant, C.: A general lower bound on Gallai-Ramsey numbers for non-bipartite graphs. Theor. Appl. Graphs 5(1), 4 (2018)
Magnant, C., Nowbandegani, P.S.: Topics in Gallai-Ramsey theory, Springer Briefs in Mathematics. Springer, Switzerland (2020)
Radziszowski, S.P.: Small Ramsey numbers. Electron. J. Combin. (1994)
Wu, H., Magnant, C., Salehi Nowbandegani, P., Xia, S.: All partitions have small parts-Gallai-Ramsey numbers of bipartite graphs. Discrete Appl. Math. 254, 196–203 (2019)
Zhang, Y., Broersma, H., Chen, Y.: On star-critical and upper size Ramsey numbers. Discrete Appl. Math. 202, 174–180 (2016)
Funding
This work is supported by the Natural Science Foundation of Guangdong (No. 2021A1515012045) and by the Science and Technology Program of Guangzhou (No. 202002030183) and by the National Natural Science Foundation of China (No. 1216073) and by the Natural Science Foundation of Qinghai (No. 2020-ZJ-924).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have not disclosed any competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Su, X., Liu, Y. Star-Critical Gallai–Ramsey Numbers of Graphs. Graphs and Combinatorics 38, 158 (2022). https://doi.org/10.1007/s00373-022-02561-4
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-022-02561-4