The Erdős–Gyárfás function with respect to Gallai-colorings

Xihe Li, Hajo Broersma*, Ligong Wang

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
57 Downloads (Pure)

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 languageEnglish
Pages (from-to)242-264
Number of pages23
JournalJournal of graph theory
Volume101
Issue number2
DOIs
Publication statusPublished - Oct 2022

Keywords

  • Erdős–Gyárfás function
  • Gallai-coloring
  • Ramsey theory
  • UT-Hybrid-D

Fingerprint

Dive into the research topics of 'The Erdős–Gyárfás function with respect to Gallai-colorings'. Together they form a unique fingerprint.

Cite this