论文标题
关于加莱色的Erdős-gyárfás的功能
The Erdős-Gyárfás function with respect to Gallai-colorings
论文作者
论文摘要
对于固定的$ p $和$ q $，如果每个$ k_p $都会收到至少$ q $不同的颜色，则据说完整图$ k_n $的边彩色$ k_n $。功能$ f（n，p，q）$是$ k_n $具有$（p，q）$ - 颜色所需的最小颜色数。该功能是大约45年前引入的，但在1997年由Erdős和Gyárfás系统地研究，现在被称为Erdős-gyárfás功能。在本文中，我们研究了$ f（n，p，q）$关于加莱色的，在那里，加莱颜色是$ k_n $的边缘颜色，没有彩虹三角形。结合了两个概念，我们考虑了功能$ g（n，p，q）$，这是加莱 - $（p，q）$ - $ k_n $所需的最低颜色数量。使用$ k_3 $的反拉姆西号，我们有$ g（n，p，q）$仅以$ 2 \ leq q \ leq p-1 $而不是平底。我们为此功能提供了一般的下限，我们研究了当$ q = p-1 $和$ p \ geq 4 $等于$ n-1 $时，当$ q = 2 $时，该功能如何从等于$ n-1 $。特别是，对于适当的$ p $和$ n $，我们证明$ g = n-c $当$ q = p-c $和$ c \ in \ {1,2 \} $，$ g $，$ g $最多最多是$ n $的$ n $时电量时，当$ q = \ lfloor \ lfloor \ sqrt \ sqrt \ sqrt {p-1} \ rfloor $ g $ n $ n $ n $ n $ n是logar in y in $ n是logar in。 q \ leq \ lfloor \ log_2（p-1）\ rfloor+1 $。
For fixed $p$ and $q$, an edge-coloring of the complete graph $K_n$ is said to be a $(p, q)$-coloring if every $K_p$ receives at least $q$ distinct colors. The function $f(n, p, q)$ is the minimum number of colors needed for $K_n$ to have a $(p, q)$-coloring. This function was introduced about 45 years ago, but was studied systematically by Erdős and Gyárfás in 1997, and is now known as the Erdős-Gyárfás function. In this paper, we study $f(n, p, q)$ with respect to Gallai-colorings, where a Gallai-coloring is an edge-coloring of $K_n$ without rainbow triangles. Combining the two concepts, we consider the function $g(n, p, q)$ that is the minimum number of colors needed for a Gallai-$(p, q)$-coloring of $K_n$. Using the anti-Ramsey number for $K_3$, we have that $g(n, p, q)$ is nontrivial only for $2\leq q\leq p-1$. We give a general lower bound for this function and we study how this function falls off from being equal to $n-1$ when $q=p-1$ and $p\geq 4$ to being $Θ(\log n)$ when $q = 2$. In particular, for appropriate $p$ and $n$, we prove that $g=n-c$ when $q=p-c$ and $c\in \{1,2\}$, $g$ is at most a fractional power of $n$ when $q=\lfloor\sqrt{p-1}\rfloor$, and $g$ is logarithmic in $n$ when $2\leq q\leq \lfloor\log_2 (p-1)\rfloor+1$.
