Multicolor star-critical Ramsey numbers and Ramsey-good graphs. (English) Zbl 1487.05173
Summary: This paper seeks to develop the multicolor version of star-critical Ramsey numbers, which serve as a measure of the strength of the corresponding Ramsey numbers. We offer several general theorems, some of which focus on Ramsey-good cases (i.e., cases in which the corresponding Ramsey number is equal to a general lower bound). We also prove some specific cases for small graphs, and conclude with a table of known multicolor star-critical Ramsey numbers.
References:
| [1] | L. Beineke and A. Schwenk, On a bipartite form of the Ramsey problem, In: Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), Congressus Numerantium, No. XV, Utilitas Math. 1976, 17-22. · Zbl 0333.05118 |
| [2] | B. Bollobás, C. Jayawardene, J. Yang, Y. Huang, C. Rousseau, and K. Zhang, On a conjecture involving cycle-complete graph Ramsey numbers, Australas. J. Combin. 22 (2000), 63-71. http://ajc.maths.uq.edu.au/pdf/22/ocr-ajc-v22-p63.pdf · Zbl 0963.05094 |
| [3] | J. Bondy and P. Erdős, Ramsey number for cycles in graphs, J. Combin. Theory Ser. B 14 (1973) 46-54. · Zbl 0248.05127 |
| [4] | L. Boza, M. Cera, P. García-Vázquez, and M. Revuelta, On the Ramsey numbers for stars versus complete graphs, Eur. J. Combin. 31 (2010), 1680-1688. · Zbl 1231.05177 |
| [5] | M. Budden and E. DeJonge, Destroying the Ramsey property by the removal of edges, Aus-tralas. J. Combin. 74 (2019), 476-485. http://ajc.maths.uq.edu.au/pdf/74/ajc v74 p476.pdf · Zbl 1419.05137 |
| [6] | M. Budden, J. Hiller, and A. Penland, Constructive methods in Gallai-Ramsey theory for hypergraphs, Integers 20A (2020), #A4. http://math.colgate.edu/ · Zbl 1439.05149 |
| [7] | S. Burr, Ramsey numbers involving graphs with long suspended paths, J. London Math. Soc. 24(2) (1981), 405-413. · Zbl 0474.05051 |
| [8] | S. Burr and P. Erdős, Generalized Ramsey numbers involving subdivision graphs, and related problems in graph theory, Ann. Discrete Math. 9 (1980), 37-42. · Zbl 0456.05047 |
| [9] | S. Burr and P. Erdős, Generalizations of a Ramsey-theoretic result of Chvátal, J. Graph The-ory 7 (1983), 39-51. · Zbl 0513.05040 |
| [10] | S. Burr and J. Roberts, On Ramsey numbers for stars, Utilitas Math. 4 (1973), 217-220. · Zbl 0293.05119 |
| [11] | G. Chartrand and S. Schuster, On the existence of specified cycles in complementary graphs, Bull. Amer. Math. Soc. 77(6) (1971), 995-998. · Zbl 0224.05121 |
| [12] | G. Chartrand and S. Schuster, On a variation of the Ramsey number, Trans. Amer. Math. Soc. 173 (1972), 353-362. · Zbl 0255.05110 |
| [13] | Y. Chen, T. Cheng, and Y. Zhang, The Ramsey numbers R(C m , K 7 ) and R(C 7 , K 8 ), Euro-pean J. Combin. 29(5) (2008), 1337-1352. · Zbl 1154.05044 |
| [14] | M. Christou, C. Iliopoulos, and M. Miller, Bipartite Ramsey numbers involving stars, stripes and trees, Electron. J. Graph Theory Appl. 1(2) (2013), 89-99. https://ejgta.org/index.php/ejgta/article/view/26 · Zbl 1306.05147 |
| [15] | V. Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977), 93. · Zbl 0351.05120 |
| [16] | V. Chvátal and F. Harary, Generalized Ramsey theory for graphs III. Small off-diagonal num-bers, Pacific J. Math. 41 (1972), 335-345. · Zbl 0227.05115 |
| [17] | R. Cowen, Deleting edges from Ramsey minimal examples, Amer. Math. Monthly 122 (2015), 681-683. · Zbl 1331.05217 |
| [18] | P. Erdős and R. Faudree, Size Ramsey functions, In: “Sets, Graphs and Numbers,” Colloq. Math. Soc. Janos Bolyai 60 (1992), 219-238. · Zbl 0794.05084 |
| [19] | P. Erdős, R. Faudree, C. Rousseau, and R. Schelp, On cycle-complete graph Ramsey num-bers, J. Graph Theory 2 (1978), 53-64. · Zbl 0383.05027 |
| [20] | R. Faudree, R. Gould, M. Jacobson, and C. Magnant, Ramsey numbers in rainbow triangle free colorings, Australas. J. Combin. 46 (2010), 269-284. http://ajc.maths.uq.edu.au/pdf/46/ajc v46 p269.pdf · Zbl 1196.05052 |
| [21] | R. Greenwood and A. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math. 7 (1955), 1-7. · Zbl 0064.17901 |
| [22] | A. Gyárfás, G. Sárközy, A. Sebő, and S. Selkow, Ramsey-type results for Gallai colorings, J. Graph Theory 64 (2010), 233-243. · Zbl 1209.05082 |
| [23] | A. Gyárfás and G. Simonyi, Edge colorings of complete graphs without tricolored triangles, J. Graph Theory 46(3) (2004), 211-216. · Zbl 1041.05028 |
| [24] | S. Haghi and H. Maimani, A. Seify, Star-critical Ramsey numbers of F n versus K 4 , Discrete Appl. Math. 217 (2017), 203-209. · Zbl 1358.05186 |
| [25] | F. Harary, Graph Theory, Addison-Wesley Publishing Company, Inc., 1969. · Zbl 0182.57702 |
| [26] | F. Harary and G. Prins, Generalized Ramsey theory for graphs, IV: the Ramsey multiplicity of a graph, Networks 4 (1974), 163-173. · Zbl 0288.05109 |
| [27] | J. Hook, The Classification of Critical Graphs and Star-Critical Ramsey Numbers, Ph.D. Thesis, Lehigh University, 2010. |
| [28] | J. Hook, Critical graphs for R(P n , P m ) and the star-critical Ramsey number for paths, Dis-cuss. Math. Graph Theory 35 (2015), 689-701. · Zbl 1327.05228 |
| [29] | J. Hook and G. Isaak, Star-critical Ramsey numbers, Discrete Appl. Math. 159 (2011), 328-334. · Zbl 1207.05212 |
| [30] | R. Irving, Generalised Ramsey numbers for small graphs, Discrete Math. 9 (1974) 251-264. · Zbl 0287.05104 |
| [31] | M. Jacobson, On the Ramsey multiplicity for stars, Discrete Math. 42 (1982), 63-66. · Zbl 0501.05045 |
| [32] | M. Jacobson, On the Ramsey number for stars and a complete graph, Ars Combin. 17 (1984), 167-172. · Zbl 0554.05050 |
| [33] | C. Jayawardene, Star-critical Ramsey numbers for cycles versus the complete graph on 5 vertices, preprint. https://arxiv.org/abs/1901.04802 |
| [34] | C. Jayawardene, D. Narváez, and S. Radziszowski, Star-critical Ramsey numbers for cycles versus K 4 , Discuss. Math. Graph Theory 41(2) (2021), 381-390. · Zbl 1458.05163 |
| [35] | Y. Li and C. Rousseau, Fan-complete Ramsey numbers, J. Graph Theory 23(4) (1996), 413-420. · Zbl 0954.05031 |
| [36] | Z. Li and Y. Li, Some star-critical Ramsey numbers, Discrete Appl. Math. 181 (2015), 301-305. · Zbl 1304.05100 |
| [37] | V. Nikiforov, The cycle-complete graph Ramsey numbers, Combin. Probab. Comput. 14(3) (2005), 349-370. · Zbl 1071.05051 |
| [38] | G. Omidi and G. Raeisi, A note on the Ramsey number of stars-complete graphs, Eur. J. Combin. 32 (2011), 598-599. · Zbl 1226.05177 |
| [39] | S. Radziszowski, Small Ramsey numbers -revision 16, Electron. J. Combin. DS1.16 (2021), 1-116. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1/pdf |
| [40] | I. Schiermeyer, All cycle-complete graph Ramsey numbers r(C m , K 6 ), J. Graph Theory 44(4) (2003), 251-260. · Zbl 1031.05086 |
| [41] | Surahmat, E. Baskoro, and H. Broersma, The Ramsey numbers of fans versus K 4 , Bull. Inst. Combin. Appl. 43 (2005), 96-102. · Zbl 1067.05049 |
| [42] | Y. Wang, Y. Li, and Y. Li, Redundant edges in Ramsey graphs, preprint. https://arxiv.org/pdf/1712.03226.pdf |
| [43] | J. Yang, Y. Huang, and K. Zhang, The value of the Ramsey number R(C n , K 4 ) is 3(n − 1) + 1 (n ≥ 4), Australas. J. Combin. 20 (1999), 205-206. http://ajc.maths.uq.edu.au/pdf/20/ocr-ajc-v20-p205.pdf · Zbl 0931.05057 |
| [44] | Y. Zhang, H. Broersma, and Y. Chen, On star-critical and upper size Ramsey numbers, Dis-crete Appl. Math. 202 (2016), 174-180. · Zbl 1330.05157 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
