Rainbow Subgraphs in Edge-colored Complete Graphs -- Answering two Questions by Erdős and Tuza
Authors:
- Maria AxenovichMAMaria Axenovich
- Felix Christian ClemenFCFelix Christian Clemen
Preprint
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.