A rainbow subgraph of a vertex-colored graph is a subgraph whose vertices have pairwise distinct colors (Angles d'Auriac et al. 2016). In a graph with an edge coloring, a rainbow subgraph is a subgraph whose edges have pairwise distinct colors.
If a rainbow subgraph is also tropical, then it is a colorful subgraph.
For a graph 
, let 
be the least number of colors in an edge
coloring of some graph on 
vertices with at least 
edges in
which every copy of 
is a rainbow subgraph. Shahab (2026) proved
 |
(1)
|
as 
,
where 
is the floor function. Together with the result
of Bucić et al. (2026) for 
, this proves the Burr-Erdős-Graham-Sós
conjecture
 |
(2)
|
for every fixed integer 
. This is Problem 809 in the Erdős
problems collection.
Chao et al. (2026) proved that a simple graph with 
edges and an edge coloring
using 
colors has at most
 |
(3)
|
rainbow triangles, meaning rainbow copies of the cycle graph 
.
The constant is sharp whenever an affine
plane of order 
exists. In that case, the extremal graphs are balanced
graph blow-ups of the complete
graph on the points of such an affine
plane, with colors assigned by parallel classes
of lines, together with possible isolated
vertices.
