DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

X.H. Li and L.G. Wang

Title:

Gallai-Ramsey numbers for rainbow $S^{+}_{3}$ and monochromatic paths

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-06-13, Revised: 2019-03-18, Accepted: 2019-10-22, https://doi.org/10.7151/dmgt.2310

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 $gr_k(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 $S^{+}_{3}$ be the graph on four vertices consisting of a triangle with a pendant edge. In this paper, we prove that $gr_k(S^{+}_{3} : P_5)=k+4$ ($k\geq 5$), $gr_k(S^{+}_{3} : mP_2)= (m-1)k+m+1$ ($k\geq 1$), $gr_k(S^{+}_{3} : P_3 \cup P_2)= k+4$ ($k\geq 5$) and $gr_k(S^{+}_{3} : 2P_3)=k+5$ ($k\geq 1$).

Keywords:

Gallai-Ramsey number, rainbow coloring, monochromatic paths

PDF
Close