Lower bounds on the Erdős–Gyárfás problem via color energy graphs

József Balogh, Sean English, Emily Heath, Robert A. Krueger

Research output: Contribution to journalArticlepeer-review


Given positive integers (Formula presented.) and (Formula presented.), a (Formula presented.) -coloring of the complete graph (Formula presented.) is an edge-coloring in which every (Formula presented.) -clique receives at least (Formula presented.) colors. Erdős and Shelah posed the question of determining (Formula presented.), the minimum number of colors needed for a (Formula presented.) -coloring of (Formula presented.). In this paper, we expand on the color energy technique introduced by Pohoata and Sheffer to prove new lower bounds on this function, making explicit the connection between bounds on extremal numbers and (Formula presented.). Using results on the extremal numbers of subdivided complete graphs, theta graphs, and subdivided complete bipartite graphs, we generalize results of Fish, Pohoata, and Sheffer, giving the first nontrivial lower bounds on (Formula presented.) for some pairs (Formula presented.) and improving previous lower bounds for other pairs.

Original languageEnglish (US)
Pages (from-to)378-409
Number of pages32
JournalJournal of Graph Theory
Issue number2
StatePublished - Jun 2023


  • color energy
  • generalized Ramsey
  • local properties

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Lower bounds on the Erdős–Gyárfás problem via color energy graphs'. Together they form a unique fingerprint.

Cite this