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

DOI10.1002/JGT.22924zbMATH Open1522.05090arXiv2102.11466MaRDI QIDQ6074587FDOQ6074587

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

Publication date: 12 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: Given positive integers $p$ and $q$, a $(p,q)$-coloring of the complete graph $K_n$ is an edge-coloring in which every $p$-clique receives at least $q$ colors. ErdH{o}s and Shelah posed the question of determining $f(n,p,q)$, the minimum number of colors needed for a $(p,q)$-coloring of $K_n$. 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 $f(n,p,q)$. 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 $f(n,p,q)$ for some pairs $(p,q)$ and improving previous lower bounds for other pairs.

Full work available at URL: https://arxiv.org/abs/2102.11466

Recommendations

• The Erdős-Gyárfás problem on generalized Ramsey numbers
• The Erdős–Gyárfás function with respect to Gallai‐colorings
• On edge colorings with at least \(q\) colors in every subset of \(p\) vertices
• Edge-coloring cliques with three colors on all 4-cliques
• On a generalized anti-Ramsey problem

zbMATH Keywords

color energylocal propertiesgeneralized Ramsey

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• On a problem of K. Zarankiewicz
• Title not available (Why is that?)
• The Erdős-Gyárfás problem on generalized Ramsey numbers
• Title not available (Why is that?)
• Repeated patterns in proper colorings
• A (5,5)-Colouring of K_n with Few Colours
• A variant of the classical Ramsey problem
• Edge-coloring cliques with three colors on all 4-cliques
• On a class of degenerate extremal graph problems
• Local properties in colored graphs, distinct distances, and difference sets
• An explicit construction for a Ramsey problem
• On edge colorings with at least \(q\) colors in every subset of \(p\) vertices
• Turán numbers of theta graphs
• The extremal number of the subdivisions of the complete bipartite graph
• Generalized Ramsey numbers: forbidding paths with few colors
• Edge-coloring cliques with many colors on subcliques
• Improved bounds for the extremal number of subdivisions
• An application of the regularity lemma in generalized Ramsey theory
• Local properties via color energy graphs and forbidden configurations
• On color isomorphic subdivisions

Cited In (8)

• The Erdős–Gyárfás function with respect to Gallai‐colorings
• Local properties via color energy graphs and forbidden configurations
• An explicit edge-coloring of \(K_n\) with six colors on every \(K_5\)
• New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
• Growth rates of the bipartite Erdős-Gyárfás function
• The Erdős-Gyárfás problem on generalized Ramsey numbers
• Rainbow subgraphs in edge-colored planar and outerplanar graphs
• New bounds on the generalized Ramsey number \(f(n, 5, 8)\)

This page was built for publication: Lower bounds on the Erdős–Gyárfás problem via color energy graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074587)