Gallai-Ramsey Numbers for Rainbow S+3and Monochromatic Paths

Xihe Li, Ligong Wang

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Motivated by Ramsey theory and other rainbow-coloring-related problems, we consider edge-colorings of complete graphs without rainbow copy of some fixed subgraphs. Given two graphs G and H, the k-colored Gallai-Ramsey number grk(G: H) is defined to be the minimum positive integer n such that every k-coloring of the complete graph on n vertices contains either a rainbow copy of G or a monochromatic copy of H. Let S3+ be the graph on four vertices consisting of a triangle with a pendant edge. In this paper, we prove that grk(S3+:P5)=k+4(k≥5) g{r-k}left({:{P-5}} \right) = k + 4\left({k \ge 5} \right), grk(S3+:mP2)=(m-1)k+m+1(k≥1) g{r-k}\left({m{P-2}} \right) = \left({m - 1} \right)k + m + 1\left({k \ge 1} \right), grk(S3+:P3?P2)=k+4(k≥5) g{r-k}\left({P-3} \cup {P-2}} \right) = k + 4\left({k \ge 5} \right) and grk(S3+:2P3)=k+5(k≥1) g{r-k}\left({2{P-3}} \right) = k + 5\left({k \ge 1} \right).

Original languageEnglish
Pages (from-to)349-362
Number of pages14
JournalDiscussiones Mathematicae - Graph Theory
Volume42
Issue number2
DOIs
StatePublished - 1 May 2022

Keywords

  • Gallai-Ramsey number
  • monochromatic paths
  • rainbow coloring

Fingerprint

Dive into the research topics of 'Gallai-Ramsey Numbers for Rainbow S+3and Monochromatic Paths'. Together they form a unique fingerprint.

Cite this