We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The Erdős–Gyárfás function with respect to Gallai‐colorings.
- Authors
Li, Xihe; Broersma, Hajo; Wang, Ligong
- Abstract
For fixed p $p$ and q $q$, an edge‐coloring of the complete graph Kn ${K}_{n}$ is said to be a (p,q) $(p,q)$‐coloring if every Kp ${K}_{p}$ receives at least q $q$ distinct colors. The function f(n,p,q) $f(n,p,q)$ is the minimum number of colors needed for Kn ${K}_{n}$ to have a (p,q) $(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) $f(n,p,q)$ with respect to Gallai‐colorings, where a Gallai‐coloring is an edge‐coloring of Kn ${K}_{n}$ without rainbow triangles. Combining the two concepts, we consider the function g(n,p,q) $g(n,p,q)$ that is the minimum number of colors needed for a Gallai‐(p,q) $(p,q)$‐coloring of Kn ${K}_{n}$. Using the anti‐Ramsey number for K3 ${K}_{3}$, we have that g(n,p,q) $g(n,p,q)$ is nontrivial only for 2≤q≤p−1 $2\le q\le 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 $n-1$ when q=p−1 $q=p-1$ and p≥4 $p\ge 4$ to being Θ(log n) ${\rm{\Theta }}(\mathrm{log}\unicode{x0200A}n)$ when q=2 $q=2$. In particular, for appropriate p $p$ and n $n$, we prove that g=n−c $g=n-c$ when q=p−c $q=p-c$ and c∈{1,2} $c\in \{1,2\}$, g $g$ is at most a fractional power of n $n$ when q=⌊p−1⌋ $q=\lfloor \sqrt{p-1}\rfloor $, and g $g$ is logarithmic in n $n$ when 2≤q≤⌊log2(p−1)⌋+1 $2\le q\le \lfloor {\mathrm{log}}_{2}(p-1)\rfloor +1$.
- Subjects
RAMSEY numbers; FRACTIONAL powers; COMPLETE graphs; RAMSEY theory
- Publication
Journal of Graph Theory, 2022, Vol 101, Issue 2, p242
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22822