Rainbow Subgraphs in Edge-colored Complete Graphs -- Answering two Questions by Erdős and Tuza

Authors:
  • MAMaria Axenovich
    Maria Axenovich
  • FCFelix Christian Clemen
    Felix Christian Clemen

Abstract
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\H{o}s and Tuza asked in $1993$ whether for any graph $F$ on $\ell$ edges and any completely balanced coloring of any sufficiently large complete graph using $\ell$ colors contains a rainbow copy of $F$. We answer this and a related question in the negative for an infinite family of graphs $F$ by giving an explicit construction of a respective completely balanced coloring.