Multicolor star-critical Ramsey numbers and Ramsey-good graphs

Mark Rowland Budden, Elijah DeJonge

Abstract


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.


Keywords


Deleted edge number, Ramsey minimal, size Ramsey number

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2022.10.1.4

References

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.

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

J. Bondy and P. Erds, Ramsey number for cycles in graphs, J. Combin. Theory Ser. B 14 (1973) 46–54.

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.

M. Budden and E. DeJonge, Destroying the Ramsey property by the removal of edges, Australas. J. Combin. 74 (2019), 476–485. http://ajc.maths.uq.edu.au/pdf/74/ajc_v74_p476.pdf

M. Budden, J. Hiller, and A. Penland, Constructive methods in Gallai-Ramsey theory for hypergraphs, Integers 20A (2020), #A4. http://math.colgate.edu/%7Eintegers/uproc4/uproc4.pdf

S. Burr, Ramsey numbers involving graphs with long suspended paths, J. London Math. Soc. 24(2) (1981), 405–413.

S. Burr and P. Erds, Generalized Ramsey numbers involving subdivision graphs, and related problems in graph theory, Ann. Discrete Math. 9 (1980), 37–42.

S. Burr and P. Erds, Generalizations of a Ramsey-theoretic result of Chvátal, J. Graph Theory 7 (1983), 39–51.

S. Burr and J. Roberts, On Ramsey numbers for stars, Utilitas Math. 4 (1973), 217–220.

G. Chartrand and S. Schuster, On the existence of specified cycles in complementary graphs, Bull. Amer. Math. Soc. 77(6) (1971), 995–998.

G. Chartrand and S. Schuster, On a variation of the Ramsey number, Trans. Amer. Math. Soc. 173 (1972), 353–362.

Y. Chen, T. Cheng, and Y. Zhang, The Ramsey numbers R(Cm, K7) and R(C7, K8), European J. Combin. 29(5) (2008), 1337–1352.

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

V. Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977), 93.

V. Chvátal and F. Harary, Generalized Ramsey theory for graphs III. Small off-diagonal numbers, Pacific J. Math. 41 (1972), 335–345.

R. Cowen, Deleting edges from Ramsey minimal examples, Amer. Math. Monthly 122 (2015), 681–683.

P. Erds and R. Faudree, Size Ramsey functions, In: “Sets, Graphs and Numbers,” Colloq. Math. Soc. Janos Bolyai 60 (1992), 219–238.

P. Erds, R. Faudree, C. Rousseau, and R. Schelp, On cycle-complete graph Ramsey numbers, J. Graph Theory 2 (1978), 53–64.

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

R. Greenwood and A. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math. 7 (1955), 1–7.

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.

A. Gyárfás and G. Simonyi, Edge colorings of complete graphs without tricolored triangles, J. Graph Theory 46(3) (2004), 211–216.

S. Haghi and H. Maimani, A. Seify, Star-critical Ramsey numbers of Fn versus K4, Discrete Appl. Math. 217 (2017), 203–209.

F. Harary, Graph Theory, Addison-Wesley Publishing Company, Inc., 1969.

F. Harary and G. Prins, Generalized Ramsey theory for graphs, IV: the Ramsey multiplicity of a graph, Networks 4 (1974), 163–173.

J. Hook, The Classification of Critical Graphs and Star-Critical Ramsey Numbers, Ph.D. Thesis, Lehigh University, 2010.

J. Hook, Critical graphs for R(Pn, Pm) and the star-critical Ramsey number for paths, Discuss. Math. Graph Theory 35 (2015), 689–701.

J. Hook and G. Isaak, Star-critical Ramsey numbers, Discrete Appl. Math. 159 (2011), 328–334.

R. Irving, Generalised Ramsey numbers for small graphs, Discrete Math. 9 (1974) 251– 264.

M. Jacobson, On the Ramsey multiplicity for stars, Discrete Math. 42 (1982), 63–66.

M. Jacobson, On the Ramsey number for stars and a complete graph, Ars Combin. 17 (1984), 167–172.

C. Jayawardene, Star-critical Ramsey numbers for cycles versus the complete graph on 5 vertices, preprint. https://arxiv.org/abs/1901.04802

C. Jayawardene, D. Narváez, and S. Radziszowski, Star-critical Ramsey numbers for cycles versus K4, Discuss. Math. Graph Theory 41(2) (2021), 381–390.

Y. Li and C. Rousseau, Fan-complete Ramsey numbers, J. Graph Theory 23(4) (1996), 413–420.

Z. Li and Y. Li, Some star-critical Ramsey numbers, Discrete Appl. Math. 181 (2015), 301–305.

V. Nikiforov, The cycle-complete graph Ramsey numbers, Combin. Probab. Comput. 14(3) (2005), 349–370.

G. Omidi and G. Raeisi, A note on the Ramsey number of stars-complete graphs, Eur. J. Combin. 32 (2011), 598–599.

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

I. Schiermeyer, All cycle-complete graph Ramsey numbers r(Cm, K6), J. Graph Theory 44(4) (2003), 251–260.

Surahmat, E. Baskoro, and H. Broersma, The Ramsey numbers of fans versus K4, Bull. Inst. Combin. Appl. 43 (2005), 96–102.

Y. Wang, Y. Li, and Y. Li, Redundant edges in Ramsey graphs, preprint. https://arxiv.org/pdf/1712.03226.pdf

J. Yang, Y. Huang, and K. Zhang, The value of the Ramsey number R(Cn, K4) 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

Y. Zhang, H. Broersma, and Y. Chen, On star-critical and upper size Ramsey numbers, Discrete Appl. Math. 202 (2016), 174–180.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

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

View EJGTA Stats