Gallai–Ramsey number for K5 ${K}_{5}$
- 15 April 2022
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 101 (3) , 455-492
Abstract
Given a graph , the ‐colored Gallai–Ramsey number is defined to be the minimum integer such that every ‐coloring of the edges of the complete graph on vertices contains either a rainbow triangle or a monochromatic copy of Fox et al. conjectured the values of the Gallai–Ramsey numbers for complete graphs. Recently, this conjecture has been verified for the first open case, when . In this paper we attack the next case, when . Surprisingly it turns out, that the validity of the conjecture depends upon the (yet unknown) value of the Ramsey number . It is known that and conjectured that . If , then Fox et al.'s conjecture is true and we present a complete proof. If, however, , then Fox et al.'s conjecture is false, meaning that exactly one of these conjectures is true while the other is false. For the case when , we show lower and upper bounds for the Gallai–Ramsey number .Keywords
This publication has 12 references indexed in Scilit:
- Gallai‐Ramsey number for K4Journal of Graph Theory, 2019
- A General Lower Bound on Gallai-Ramsey Numbers for Non-Bipartite GraphsTheory and Applications of Graphs, 2018
- The Erdős–Hajnal conjecture for rainbow trianglesJournal of Combinatorial Theory, Series B, 2015
- Rainbow generalizations of Ramsey theory - a dynamic surveyTheory and Applications of Graphs, 2014
- Ramsey‐type results for Gallai coloringsJournal of Graph Theory, 2009
- Subgraph Counting Identities and Ramsey NumbersJournal of Combinatorial Theory, Series B, 1997
- R(4, 5) = 25Journal of Graph Theory, 1995
- Edge-colored complete graphs with precisely colored subgraphsCombinatorica, 1983
- Transitiv orientierbare GraphenActa Mathematica Hungarica, 1967
- Combinatorial Relations and Chromatic GraphsCanadian Journal of Mathematics, 1955