Gallai–Ramsey Numbers for a Class of Graphs with Five Vertices

Xihe Li, Ligong Wang

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Given two graphs G and H, the k-colored Gallai–Ramsey number grk(G: H) is defined to be the minimum 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. In this paper, we consider grk(K3: H) , where H is a connected graph with five vertices and at most six edges. There are in total thirteen graphs in this graph class, and the Gallai–Ramsey numbers for eight of them have been studied step by step in several papers. We determine all the Gallai–Ramsey numbers for the remaining five graphs, and we also obtain some related results for a class of unicyclic graphs. As applications, we find the mixed Ramsey spectra S(n; H, K3) for these graphs by using the Gallai–Ramsey numbers.

Original languageEnglish
Pages (from-to)1603-1618
Number of pages16
JournalGraphs and Combinatorics
Volume36
Issue number6
DOIs
StatePublished - 1 Nov 2020

Keywords

  • Gallai–Ramsey number
  • Mixed Ramsey spectrum
  • Rainbow triangle

Fingerprint

Dive into the research topics of 'Gallai–Ramsey Numbers for a Class of Graphs with Five Vertices'. Together they form a unique fingerprint.

Cite this