Abstract
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.).
Original language | English |
---|---|
Pages (from-to) | 242-264 |
Number of pages | 23 |
Journal | Journal of Graph Theory |
Volume | 101 |
Issue number | 2 |
DOIs | |
State | Published - Oct 2022 |
Keywords
- Erdős–Gyárfás function
- Gallai-coloring
- Ramsey theory