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

10.22108/toc.2024.140839.2157

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

Articles in Press, Accepted Manuscript
Available Online from 13 August 2024

Files

History

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

Share

How to cite

Statistics