Gallai-Ramsey Numbers for Rainbow S3+S_3^ + and Monochromatic Paths
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2022-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2310 |
| _version_ | 1827844619294998528 |
|---|---|
| author | Li Xihe Wang Ligong |
| author_facet | Li Xihe Wang Ligong |
| author_sort | Li Xihe |
| collection | DOAJ |
| description | 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+S_3^ + 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( {S_3^ + :{P_5}} \right) = k + 4\left( {k \ge 5} \right), grk(S3+:mP2)=(m-1)k+m+1(k≥1)g{r_k}\left( {S_3^ + :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( {S_3^ + :{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( {S_3^ + :2{P_3}} \right) = k + 5\left( {k \ge 1} \right). |
| first_indexed | 2024-03-12T08:44:29Z |
| format | Article |
| id | doaj.art-06469fed6af54b5e9036264a9e760df6 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:44:29Z |
| publishDate | 2022-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-06469fed6af54b5e9036264a9e760df62023-09-02T16:29:34ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922022-05-0142234936210.7151/dmgt.2310Gallai-Ramsey Numbers for Rainbow S3+S_3^ + and Monochromatic PathsLi Xihe0Wang Ligong1School of Mathematics and Statistics, Northwestern Polytechnical University, Xi’an, Shaanxi 710129, P.R.ChinaXi’an-Budapest Joint Research Center for Combinatorics, Northwestern Polytechnical University, Xi’an, Shaanxi 710129, P.R.ChinaMotivated 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+S_3^ + 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( {S_3^ + :{P_5}} \right) = k + 4\left( {k \ge 5} \right), grk(S3+:mP2)=(m-1)k+m+1(k≥1)g{r_k}\left( {S_3^ + :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( {S_3^ + :{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( {S_3^ + :2{P_3}} \right) = k + 5\left( {k \ge 1} \right).https://doi.org/10.7151/dmgt.2310gallai-ramsey numberrainbow coloringmonochromatic paths05c1505c5505d10 |
| spellingShingle | Li Xihe Wang Ligong Gallai-Ramsey Numbers for Rainbow S3+S_3^ + and Monochromatic Paths Discussiones Mathematicae Graph Theory gallai-ramsey number rainbow coloring monochromatic paths 05c15 05c55 05d10 |
| title | Gallai-Ramsey Numbers for Rainbow S3+S_3^ + and Monochromatic Paths |
| title_full | Gallai-Ramsey Numbers for Rainbow S3+S_3^ + and Monochromatic Paths |
| title_fullStr | Gallai-Ramsey Numbers for Rainbow S3+S_3^ + and Monochromatic Paths |
| title_full_unstemmed | Gallai-Ramsey Numbers for Rainbow S3+S_3^ + and Monochromatic Paths |
| title_short | Gallai-Ramsey Numbers for Rainbow S3+S_3^ + and Monochromatic Paths |
| title_sort | gallai ramsey numbers for rainbow s3 s 3 and monochromatic paths |
| topic | gallai-ramsey number rainbow coloring monochromatic paths 05c15 05c55 05d10 |
| url | https://doi.org/10.7151/dmgt.2310 |
| work_keys_str_mv | AT lixihe gallairamseynumbersforrainbows3s3andmonochromaticpaths AT wangligong gallairamseynumbersforrainbows3s3andmonochromaticpaths |