Extremal problems and results related to Gallai-colorings

Abstract

A Gallai-coloring (Gallai-$k$-coloring) is an edge-coloring (with colors from $\{1,2,\dots ,k\}$) of a complete graph without rainbow triangles. Given a graph $H$ and a positive integer $k$, the $k$-colored Gallai-Ramsey number $G{R}_k(H)$ is the minimum integer $n$ such that every Gallai-$k$-coloring of the complete graph $K_n$ contains a monochromatic copy of $H$. In this paper, we consider two extremal problems related to Gallai-$k$-colorings. First, we determine upper and lower bounds for the maximum number of edges that are not contained in any rainbow triangle or monochromatic triangle in a $k$-edge-coloring of $K_n$. Second, for $n\ge G{R}_k(K_3)$, we determine upper and lower bounds for the minimum number of monochromatic triangles in a Gallai-$k$-coloring of $K_n$, yielding the exact value for $k=3$. Furthermore, we determine the Gallai-Ramsey number $G{R}_k(K_4+e)$ for the graph on five vertices consisting of a $K_4$ with a pendant edge.

20 pages, 1 figure

References in corpus (2)

• Non-three-colorable common graphs exist
• Gallai-Ramsey numbers for graphs with five vertices of chromatic number four