Skip to main content

Advertisement

Log in

Ramsey Numbers of Stripes Versus Trees and Unicyclic Graphs

  • Published:
Journal of the Operations Research Society of China Aims and scope Submit manuscript

Abstract

For graphs G and H, the Ramsey number R(GH) is the minimum integer N such that any coloring of the edges of the complete graph \(K_N\) in red or blue yields a red G or a blue H. Denote the union of t disjoint copies of a graph F by tF. We call \(tK_2\) a stripe. In this paper, we completely determine Ramsey numbers of stripes versus trees and unicyclic graphs. Our result also implies that a tree is \(tK_2\)-good if and only if the independence number of this tree is no less than t. As an application, we improve the known Ramsey numbers of stars versus fan graphs. Moreover, we determine the bipartite Ramsey numbers of a connected bipartite graph versus stripes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

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

    Article  MathSciNet  MATH  Google Scholar 

  2. Cockayne, E., Lorimer, P.: On Ramsey graph number for star and stripes. Can. Math. Bull. 18, 31–34 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  3. Zhang, Y., Broersma, H., Chen, Y.: Ramsey numbers of trees versus fans. Discrete Math. 338, 994–999 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  4. Burr, S., Erdős, P., Spencer, J.: Ramsey theorems for multiple copies of graphs. Trans. Am. Math. Soc. 209, 87–99 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  5. Burr, S.: On the Ramsey numbers \(r(G, nH)\) and \(r(nG, nH)\) when \(n\) is large. Discrete Math. 65, 215–229 (1987)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  8. Allen, P., Brightwell, G., Skokan, J.: Ramsey-goodness—and otherwise. Combinatorica 33, 125–160 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  9. Balla, I., Pokrovskiy, A., Sudakov, B.: Ramsey goodness of bounded degree trees. Combin. Prob. Comput. 27, 289–309 (2018)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  11. Lin, Q., Li, Y., Dong, L.: Ramsey goodness and generalized stars. Eur. J. Combin. 31(5), 1228–1234 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  12. Lin, Q., Peng, X.: Large book-cycle Ramsey numbers. SIAM J. Discrete Math. 35, 532–545 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  13. Nikiforov, V., Rousseau, C.: Large generalized books are \(p\)-good. J. Combin. Theory Ser. B 92, 85–97 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  14. Nikiforov, V., Rousseau, C.: Ramsey goodness and beyond. Combinatorica 29, 227–262 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  15. Pokrovskiy, A., Sudakov, B.: Ramsey goodness of paths. J. Combin. Theory Ser. B 122, 384–390 (2017)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  17. Hu, S., Peng, Y.: The Ramsey number for a forest versus disjoint union of complete graphs. Graphs Combin. 39, 26 (2023)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We are thankful to the reviewers for reading the manuscript very carefully and giving us valuable comments to help improve the presentation.

Author information

Authors and Affiliations

Authors

Contributions

Si-Nan Hu and Yue-Jian Peng were contribute equally to the paper.

Corresponding author

Correspondence to Yue-Jian Peng.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

This work was supported by the National Natural Science Foundation of China (No. 11931002).

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hu, SN., Peng, YJ. Ramsey Numbers of Stripes Versus Trees and Unicyclic Graphs. J. Oper. Res. Soc. China 13, 297–312 (2025). https://doi.org/10.1007/s40305-023-00494-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40305-023-00494-0

Keywords

Mathematics Subject Classification