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

DOI10.1002/JGT.22924MaRDI QIDQ6074587zbMATH OpenFDO

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)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

color energylocal propertiesgeneralized Ramsey

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(8)

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

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)