×

Weakened Gallai-Ramsey numbers. (English) Zbl 1413.05259

Summary: In the Ramsey theory of graphs, one seeks to determine the value of the Ramsey number \(\operatorname{r}^t(n)\), defined to be the least natural number \(p\) such that every coloring of the edges of \(K_p\) using \(t\) colors results in a monochromatic copy of \(K_n\) in some color. In this paper, we demonstrate the standard techniques used for finding bounds for Ramsey numbers by combining two standard generalizations of \(\operatorname{r}^t(n)\). First, we restrict our attention to Gallai colorings: those that avoid rainbow triangles. Within this setting, we then focus on finding subgraphs isomorphic to \(K_n\) that are spanned by edges using at most \(s\geq t-1\) colors. The resulting generalization of \(\operatorname{r}^t(n)\) is called a weakened Gallai-Ramsey number, denoted \(\operatorname{gr}_s^t(n)\). As such, we determine several explicit small values and prove a few general properties of such numbers.

MSC:

05C55 Generalized Ramsey theory
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: EMIS