Counting edge-colorings of a complete graph avoiding a rainbow K4
Abstract
For $k, r, n$ natural numbers let ρr,k(Kn) be the number of r-edge-colorings of Kn that do not contain a rainbow copy of a Kk, that is, a copy of Kk in which all edges receive different colors. When k=3, the quantity ρr,3(Kn) represents the number of Gallai Colorings. It was proved by Balogh and Li and independently by Bastos, Benevides and Han, that most of the Gallai colorings are 2-colorings, for n large. A natural analogue conjecture would be that when k=4, r≥ 5 and n large, most rainbow-K4-free r-edge-colorings are $5$-colorings. We show that this is not true in general and identify an exact threshold for r where this ceases to be true. For the range where the conjecture is false, we determine the exponential growth of ρr,4(Kn) for every fixed r. More precisely, for 6≤ r≤24, we prove that ρr,4(Kn)=(binomr5+o(1))5binomn2; and for each r≥25, the proportion using at most five colors tends to zero, and ρr,4(Kn)=r(n2/4)+o(n2). A bipartite construction, with all edges within the two parts assigned one common color, achieves the latter exponential growth rate. The lower bounds can be easily generalized for every k. Those results are related to other recent results about counting colorings that avoid rainbow cliques or given rainbow patterns in general. Our proof combines hypergraph containers with the graph removal lemma, structural estimates for color palettes and a refined count of colorings close to a fixed five-color palette.
Related
- Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences
- Rainbow connecting $2$-colorings of super-Dirac graphs
- Sampling Line-Graph Colorings with Constant Extra Colors
- Local Ore Conditions for Rainbow Pancyclicity and Vertex-Pancyclicity in Graph Systems
- Colorings breaking prescribed families of graph automorphisms
BibTeX
@misc{benevides2026counting,
title = {{Counting edge-colorings of a complete graph avoiding a rainbow $K_4$}},
author = {Fabricio S. Benevides and Josefran de O. Bastos},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23179},
eprint = {2609.23179},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23179},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Counting edge-colorings of a complete graph avoiding a rainbow K_4
AU - Fabricio S. Benevides
AU - Josefran de O. Bastos
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2609.23179
UR - https://arxiv.org/abs/2609.23179
AB - For $k, r, n$ natural numbers let ρ_r,k(K_n) be the number of r-edge-colorings of K_n that do not contain a rainbow copy of a K_k, that is, a copy of K_k in which all edges receive different colors. When k=3, the quantity ρ_r,3(K_n) represents the number of Gallai Colorings. It was proved by Balogh and Li and independently by Bastos, Benevides and Han, that most of the Gallai colorings are 2-colorings, for n large. A natural analogue conjecture would be that when k=4, r≥ 5 and n large, most rainbow-K_4-free r-edge-colorings are $5$-colorings. We show that this is not true in general and identify an exact threshold for r where this ceases to be true. For the range where the conjecture is false, we determine the exponential growth of ρ_r,4(K_n) for every fixed r. More precisely, for 6≤ r≤24, we prove that ρ_r,4(K_n)=(binomr5+o(1))5^binomn2; and for each r≥25, the proportion using at most five colors tends to zero, and ρ_r,4(K_n)=r^(n^2/4)+o(n^2). A bipartite construction, with all edges within the two parts assigned one common color, achieves the latter exponential growth rate. The lower bounds can be easily generalized for every k. Those results are related to other recent results about counting colorings that avoid rainbow cliques or given rainbow patterns in general. Our proof combines hypergraph containers with the graph removal lemma, structural estimates for color palettes and a refined count of colorings close to a fixed five-color palette.
ER -