The Erdős–Gyárfás function with respect to Gallai‐colorings. Issue 2 (21st March 2022)

• Record Type: Journal Article
• Authors: Li, Xihe; Broersma, Hajo; Wang, Ligong
• Is Part Of: Journal of graph theory. Volume 101:Issue 2(2022)
• Page Start: 242
• Page End: 264
• Publication Date: 2022-03-21
• Subjects: Erdős–Gyárfás function -- Gallai‐coloring -- Ramsey theory; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22822
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: For fixed p $p$ and q $q$, an edge‐coloring of the complete graph K n ${K}_{n}$ is said to be a ( p, q ) $(p, q)$ ‐coloring if every K p ${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 K n ${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 K n ${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 K n ${K}_{n}$ . Using the anti‐Ramsey number for K 3 ${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 ≤ ⌊ log 2 ( p − 1 ) ⌋ + 1 $2\le q\le \lfloor {\mathrm{log}}_{2}(p-1)\rfloor +1$ .