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 language | English |
---|---|
Pages (from-to) | 349-362 |
Number of pages | 14 |
Journal | Discussiones Mathematicae - Graph Theory |
Volume | 42 |
Issue number | 2 |
DOIs | |
State | Published - 1 May 2022 |
Keywords
- Gallai-Ramsey number
- monochromatic paths
- rainbow coloring