Star-critical connected Ramsey numbers for 2-colorings of complete graphs

Document Type : Research Paper

Authors

1 Department of Mathematics, Central University of Haryana, Haryana, India

2 Department of Mathematics, Central University of Haryana, Haryana, India.

3 Department of Mathematics and Computer Science, Western Carolina University, Cullowhee, NC 28723

Abstract

This paper builds upon Sumner's work by further investigating the concept of connected Ramsey numbers, specifically focusing on star-critical connected Ramsey numbers. We obtain star-critical connected Ramsey numbers for several cases of trees versus complete graphs, stars versus stars, and paths versus paths. The connected Ramsey number for a star versus $K_3$ is also evaluated. Exact values are also obtained for the connected Ramsey numbers of $K_{1,n}$ versus $K_3$. This research explores the interplay between connectivity and graph coloring within the context of Ramsey theory.

Keywords

Main Subjects

References

[1] J. Bosák, A. Rosa and Š. Znám, On decompositions of complete graphs into factors with given diameters, Proc. Colloq., Tihany, 1966, Academic Press, New York-London, 1968 37–56.
[2] M. Budden, Ramsey numbers for connected 2-colorings of complete graphs, Theory Appl. Graphs, 10 no. 1 (2023) Art. 7 10 pp.
[3] M. Budden, Star-critical Ramsey numbers for graphs, SpringerBriefs in Mathematics, Springer, Cham, 2023.
[4] M. Budden and T. Wimbish, Connected Ramsey numbers involving trees, under review.
[5] L. Gerencsér and A. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 10 (1967) 167–170.
[6] F. Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. 
[7] F. Harary, Recent results on generalized Ramsey theory for graphs, Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972), Lecture Notes in Math., 303, Springer, Berlin New York, 1972 125–138.
[8] J. Hook, The classification of critical graphs and star-critical Ramsey numbers, dissertation, Lehigh University, 2010.
[9] J. Hook and G. Isaak, Star-critical Ramsey numbers, Discrete Appl. Math., 159 no. 5 (2011) 328–334.
[10] C. Magnant and P. Salehi Nowbandegani, Topics in Gallai-Ramsey theory, SpringerBriefs in Mathematics, Springer, Cham, 2020.
[11] S. Radziszowski, Small Ramsey numbers- revision #17, Electron. J. Combin., DS1.17 (2024) 133 pp.
[12] F. Ramsey, On a problem of formal logic, Proc. London Math. Soc. (2), 30 no. 4 (1929) 264–286.
[13] D. Sumner, The connected Ramsey number, Discrete Math., 22 no. 1 (1978) 49–55.
Transactions on Combinatorics
Volume 14, Issue 4 - Serial Number 4
December 2025
Pages 211-222

Files

History

  • Receive Date: 28 February 2024
  • Revise Date: 01 August 2024
  • Accept Date: 13 August 2024
  • Published Online: 01 December 2025

Share

How to cite

Statistics