## Star-critical Ramsey numbers for hexagon

### Tomasz Dzido

DOI: http://dx.doi.org/10.15439/2023F8192

Citation: Communication Papers of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 37, pages 75–80 (2023)

Abstract. Erd\''{o}s and Faudree stated that it is an interesting problem to determine all the graph pairs which are Ramsey-full. For even cycles, they only showed that the pair $(C\_4, C\_4)$ is Ramsey-full. It turns out that this statement cannot be applied to longer even cycles. Wu, Sun and Radziszowski obtained that the pair $(C\_n, C\_4)$ for $n>4$ is not Ramsey-full. In this article we will show that the pairs $(C\_n, C\_6)$ for different values of $n$ are also not Ramsey-full.

### References

- S. Brandt, “A sufficient condition for all short cycles,” Discrete Appl. Math., vol. 79, 1997, pp. 63–66.
- L. Caccetta, K. Vijayan, “Maximal cycles in graphs,” Disc. Math., vol. 98, 1991, pp. 1–7.
- P. Erdös, R. J. Faudree, “Size Ramsey functions,” Sets, Graphs and Numbers, 1991, pp. 219–238.
- Z. Füredi, D. S. Gunderson, “Extremal Numbers for Odd Cycles,” Combinatorics, Probability and Computing, vol. 24(4), 2014, pp. 641–645.
- G. Frederickson, N. Lynch, “Electing a leader in a synchronous ring,” Journal of Association for Computing Machinery, vol. 34, 1987, pp. 98–115.
- J. Hook, G. Isaak, “Star-critical Ramsey numbers,” Discrete Appl. Math., vol. 159, 2011, pp. 328–334.
- G. Károlyi and V. Rosta, “Generalized and geometric Ramsey numbers for cycles,” Theoret. Comput. Sci., vol. 263, 2001, pp. 87–98.
- B. Li, B. Ning, “Exact bipartite Turán numbers of large even cycles,” Journal of Graph Theory, vol. 97(4), 2021, pp. 642–656.
- Y. Liu, Y. Chen, “Star-critical Ramsey Numbers of Wheels Versus Odd Cycles,” Acta Mathematicae Applicatae Sinica, English Series, vol. 38(4), 2022, pp. 916–924.
- S. P. Radziszowski, “Small Ramsey numbers,” Electron. J. Combin., 2021, DS1.16.
- V. Rosta, “Ramsey Theory Applications,” Electronic Journal of Combinatorics, 2004, Dynamic Survey 13.
- M. Snir, “On parallel searching,” SIAM Journal Computing, vol. 14, 1985, pp. 688–708.
- D. R. Woodall, “Maximal circuits of graphs I,” Acta Math. Acad. Sci. Hungar., vol. 28, 1976, pp. 77–80.
- Y.L. Wu, Y.Q. Sun, S. Radziszowski, “Wheel and star-critical Ramsey numbers for quadrilateral,” Discrete Appl. Math., vol. 186, 2015, pp. 260–271.
- Y. Yuansheng, P. Rowlison, “On graphs without 6-cycles and related Ramsey numbers,” Utilitas Mathematica, vol. 44, 1993, pp. 192–196.
- Y. Zhang, H. Broersma, Y. Chen, “On star-critical and upper size Ramsey numbers,” Discrete Appl. Math., vol. 202, 2016, pp. 174–180.