Rainbow subgraphs in edge‐colored complete graphs: Answering two questions by Erdős and Tuza

Abstract

An edge‐coloring of a complete graph with a set of colors is called completely balanced if any vertex is incident to the same number of edges of each color from . Erdős and Tuza asked in 1993 whether for any graph on edges and any completely balanced coloring of any sufficiently large complete graph using colors contains a rainbow copy of . 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 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 .