2022/09/28 by Axenovich, Maria, Clemen, Felix Christian
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2209.13867
An edge-coloring of a complete graph with a set of colors C is called completely balanced if any vertex is incident to the same number of edges of each color from C. Erdős and Tuza asked in 1993 whether for any graph F on ℓ edges and any completely balanced coloring of any sufficiently large complete graph using ℓ colors contains a rainbow copy of F. This question was restated by Erdős in his list of ``Some of my favourite problems on cycles and colourings''. We answer this question in the negative for most cliques F=Kq by giving explicit constructions of respective completely balanced colorings. Further, we answer a related question concerning completely balanced colorings of complete graphs with more colors than the number of edges in the graph F.