TY - JOUR
T1 - The Erdős–Gyárfás function with respect to Gallai-colorings
AU - Li, Xihe
AU - Broersma, Hajo
AU - Wang, Ligong
N1 - Funding Information:
The authors are grateful to the anonymous referees for valuable comments, suggestions, and corrections which improved the presentation of this paper. Supported by the National Natural Science Foundation of China (No. 11871398) and China Scholarship Council (No. 201906290174).
Publisher Copyright:
© 2022 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.
PY - 2022/10
Y1 - 2022/10
N2 - For fixed (Formula presented.) and (Formula presented.), an edge-coloring of the complete graph (Formula presented.) is said to be a (Formula presented.) -coloring if every (Formula presented.) receives at least (Formula presented.) distinct colors. The function (Formula presented.) is the minimum number of colors needed for (Formula presented.) to have a (Formula presented.) -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 (Formula presented.) with respect to Gallai-colorings, where a Gallai-coloring is an edge-coloring of (Formula presented.) without rainbow triangles. Combining the two concepts, we consider the function (Formula presented.) that is the minimum number of colors needed for a Gallai- (Formula presented.) -coloring of (Formula presented.). Using the anti-Ramsey number for (Formula presented.), we have that (Formula presented.) is nontrivial only for (Formula presented.). We give a general lower bound for this function and we study how this function falls off from being equal to (Formula presented.) when (Formula presented.) and (Formula presented.) to being (Formula presented.) when (Formula presented.). In particular, for appropriate (Formula presented.) and (Formula presented.), we prove that (Formula presented.) when (Formula presented.) and (Formula presented.), (Formula presented.) is at most a fractional power of (Formula presented.) when (Formula presented.), and (Formula presented.) is logarithmic in (Formula presented.) when (Formula presented.).
AB - For fixed (Formula presented.) and (Formula presented.), an edge-coloring of the complete graph (Formula presented.) is said to be a (Formula presented.) -coloring if every (Formula presented.) receives at least (Formula presented.) distinct colors. The function (Formula presented.) is the minimum number of colors needed for (Formula presented.) to have a (Formula presented.) -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 (Formula presented.) with respect to Gallai-colorings, where a Gallai-coloring is an edge-coloring of (Formula presented.) without rainbow triangles. Combining the two concepts, we consider the function (Formula presented.) that is the minimum number of colors needed for a Gallai- (Formula presented.) -coloring of (Formula presented.). Using the anti-Ramsey number for (Formula presented.), we have that (Formula presented.) is nontrivial only for (Formula presented.). We give a general lower bound for this function and we study how this function falls off from being equal to (Formula presented.) when (Formula presented.) and (Formula presented.) to being (Formula presented.) when (Formula presented.). In particular, for appropriate (Formula presented.) and (Formula presented.), we prove that (Formula presented.) when (Formula presented.) and (Formula presented.), (Formula presented.) is at most a fractional power of (Formula presented.) when (Formula presented.), and (Formula presented.) is logarithmic in (Formula presented.) when (Formula presented.).
KW - Erdős–Gyárfás function
KW - Gallai-coloring
KW - Ramsey theory
KW - UT-Hybrid-D
UR - http://www.scopus.com/inward/record.url?scp=85126729690&partnerID=8YFLogxK
U2 - 10.1002/jgt.22822
DO - 10.1002/jgt.22822
M3 - Article
AN - SCOPUS:85126729690
SN - 0364-9024
VL - 101
SP - 242
EP - 264
JO - Journal of graph theory
JF - Journal of graph theory
IS - 2
ER -