Gallai-Ramsey numbers for rainbow S+3 and monochromatic paths
Author(s) -
Xihe Li,
Ligong Wang
Publication year - 2020
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2310
Subject(s) - monochromatic color , rainbow , mathematics , combinatorics , ramsey's theorem , physics , optics , graph
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 GallaiRamsey 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 S 3 be the graph on four vertices consisting of a triangle with a pendant edge. In this paper, we prove that grk(S + 3 : P5) = k+ 4 (k ≥ 5), grk(S + 3 : mP2) = (m− 1)k+m+ 1 (k ≥ 1), grk(S 3 : P3 ∪ P2) = k + 4 (k ≥ 5) and grk(S + 3 : 2P3) = k + 5 (k ≥ 1).
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom