Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Gallai–Ramsey Numbers for Rainbow Paths

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

Given graphs G and H and a positive integer k, the Gallai–Ramsey number, denoted by \(gr_{k}(G : H)\) is defined to be the minimum integer n such that every coloring of \(K_{n}\) using at most k colors will contain either a rainbow copy of G or a monochromatic copy of H. We consider this question in the cases where \(G \in \{P_{4}, P_{5}\}\). In the case where \(G = P_{4}\), we completely solve the Gallai–Ramsey question by reducing to the 2-color Ramsey numbers. In the case where \(G = P_{5}\), we conjecture that the problem reduces to the 3-color Ramsey numbers and provide several results in support of this conjecture.

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

Access this article

Log in via an institution

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.

Institutional subscriptions

Similar content being viewed by others

References

  1. Burr, S.A., Roberts, J.A.: On Ramsey numbers for stars. Utilitas Math. 4, 217–220 (1973)

    MathSciNet  MATH  Google Scholar 

  2. Chartrand, G., Lesniak, L., Zhang, P.: Graphs and Digraphs, 5th edn. CRC Press, Boca Raton (2011)

    MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  4. Erdős, P.: Some remarks on the theory of graphs. Bull. Am. Math. Soc. 53, 292–294 (1947)

    Article  MathSciNet  Google Scholar 

  5. Fujita, S., Magnant, C., Ozeki, K.: Rainbow generalizations of Ramsey theory: a survey. Graphs Combin. 26, 1–30 (2010)

    Article  MathSciNet  Google Scholar 

  6. Fujita, S., Magnant, C., Ozeki, K.: Rainbow generalizations of Ramsey theory: a dynamic survey. Theor. Appl. Graphs. (2014). https://doi.org/10.20429/tag.2014.000101

    Article  MATH  Google Scholar 

  7. Gyárfás, A., Lehel, J., Schelp, R.H.: Finding a monochromatic subgraph or a rainbow path. J. Graph Theory 54, 1–12 (2007)

    Article  MathSciNet  Google Scholar 

  8. Gyárfás, A., Sárközy, G.N.: Ramsey number of a connected triangle matching. J. Graph Theory 83, 109–119 (2016)

    Article  MathSciNet  Google Scholar 

  9. Thomason, A., Wagner, P.: Complete graphs with no rainbow path. J. Graph Theory 54, 261–266 (2007)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors are grateful to the anonymous referees for their valuable comments, suggestions and corrections which improved the presentation of this paper.

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Northwestern Polytechnical University, Xi’an, 710129, Shaanxi, People’s Republic of China

    Xihe Li & Ligong Wang

  2. Xi’an-Budapest Joint Research Center for Combinatorics, Northwestern Polytechnical University, Xi’an, 710129, Shaanxi, People’s Republic of China

    Xihe Li & Ligong Wang

  3. Department of Mathematics, Clayton State University, Morrow, GA, 30260, USA

    Pierre Besse, Colton Magnant & Noah Watts

  4. Academy of Plateau Science and Sustainability, Xining, 810008, Qinghai, People’s Republic of China

    Colton Magnant

Authors
  1. Xihe Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pierre Besse
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Colton Magnant
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ligong Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Noah Watts
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Colton Magnant.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Research partially supported by National Natural Science Foundation of China (No. 11871398).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, X., Besse, P., Magnant, C. et al. Gallai–Ramsey Numbers for Rainbow Paths. Graphs and Combinatorics 36, 1163–1175 (2020). https://doi.org/10.1007/s00373-020-02175-8

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-020-02175-8

Keywords

Search

Navigation