Logo PTI Logo FedCSIS

Communication Papers of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 37

Star-critical Ramsey numbers for hexagon

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 ()

Full text

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

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