Premium
Gallai‐Ramsey number for K 4
Author(s) -
Liu Henry,
Magnant Colton,
Saito Akira,
Schiermeyer Ingo,
Shi Yongtang
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22514
Subject(s) - combinatorics , mathematics , ramsey's theorem , conjecture , monochromatic color , rainbow , graph , integer (computer science) , discrete mathematics , computer science , physics , quantum mechanics , programming language , botany , biology
Given a graph H , the k ‐colored Gallai‐Ramsey number g r k ( K 3 : H )is defined to be the minimum integer n such that every k ‐coloring (using all k colors) of the complete graph on n vertices contains either a rainbow triangle or a monochromatic copy of H . Recently, Fox et al [J. Combin. Theory Ser. B, 111 (2015), pp. 75–125] conjectured the value of the Gallai‐Ramsey numbers for complete graphs. We verify this conjecture for the first open case, where H = K 4 .