论文标题
边缘彩色完整图中的彩虹子图 - 回答了Erdős和Tuza的两个问题
Rainbow Subgraphs in Edge-colored Complete Graphs -- Answering two Questions by Erdős and Tuza
论文作者
论文摘要
如果有任何顶点与$ c $相同的每种颜色的边缘数量，则具有一组颜色$ c $的完整图的边缘色被称为完全平衡。 Erdős和Tuza以$ 1993的价格询问$ \ ell $边缘上的任何图表$ f $以及使用$ \ ell $颜色的任何足够大的完整图的任何完全平衡的颜色包含$ f $的彩虹副本。埃尔德（Erd）在他的``我最喜欢的循环和颜色问题''列表中重申了这个问题。我们通过提供各自完全平衡的颜色的明确构造，以大多数集团的否定性回答这个问题。此外，我们回答了一个相关的问题，即完全平衡的完整图形颜色，其颜色比图$ f $中的边数的数量更多。
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 $\ell$ edges and any completely balanced coloring of any sufficiently large complete graph using $\ell$ 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=K_q$ 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$.
