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 -