论文标题
与加莱色有关的极端问题和结果
Extremal problems and results related to Gallai-colorings
论文作者
论文摘要
Gallai颜色（Gallai-$ k $ - 颜色）是一个边缘色（带有$ \ {1，2，\ ldots，k \} $的颜色，无彩虹三角形。给定图形$ h $和一个正整数$ k $，$ k $颜色的gallai-ramsey number $ gr_k（h）$是最小整数$ n $，因此每个gallai- $ k $ coloring the gallai- $ k $ - 完整的图形$ k_n $都包含$ h $ $ h $的单色副本。在本文中，我们考虑了与Gallai-$ K $颜色有关的两个极端问题。首先，我们确定在$ k_n $的$ k $ - 边缘颜色中的任何彩虹三角或单色三角形中未包含的最大边数的上限和下限。其次，对于$ n \ geq gr_k（k_3）$，我们确定最小单色三角形数量的上限和下限，以加莱 - $ k $ - 颜色为$ k_ {n} $，得出$ k = 3 $的确切值。此外，我们确定Gallai-ramsey编号$ gr_k（k_4+e）$用于图形上的五个顶点，由$ k_4 $组成，带有吊坠边缘。
A Gallai-coloring (Gallai-$k$-coloring) is an edge-coloring (with colors from $\{1, 2, \ldots, k\}$) of a complete graph without rainbow triangles. Given a graph $H$ and a positive integer $k$, the $k$-colored Gallai-Ramsey number $GR_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\geq GR_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 $GR_k(K_4+e)$ for the graph on five vertices consisting of a $K_4$ with a pendant edge.
