2020/06/17 by Alex Cameron, Cameron, Alex, Emily Heath +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2006.09577
openalex publication_date 2020/06/17 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
A (p,q)-coloring of a graph G is an edge-coloring of G which assigns at least q colors to each p-clique. The problem of determining the minimum number of colors, f(n,p,q), needed to give a (p,q)-coloring of the complete graph Kn is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers rk(p). The best-known general upper bound on f(n,p,q) was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where p=q have been obtained only for p∈\4,5\, each of which was proved by giving a deterministic construction which combined a (p,p-1)-coloring using few colors with an algebraic coloring. In this paper, we provide a framework for proving new upper bounds on f(n,p,p) in the style of these earlier constructions. We characterize all colorings of p-cliques with p-1 colors which can appear in our modified version of the (p,p-1)-coloring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying (p,p)-colorings, which would otherwise make this problem intractable for large values of p. In addition, we generalize our algebraic coloring from the p=5 setting and use this to give improved upper bounds on f(n,6,6) and f(n,8,8).