Monochromatic Graph Decompositions Inspired by Anti-Ramsey Theory and Parity Constraints - Yair Caro; Zsolt Tuza (Mathematics)
We open here many new tracks of research in anti-Ramsey Theory, considering edge-coloring problems inspired by rainbow coloring and further by odd colorings and conflict-free colorings. Let G be a graph and <semantics>F</semantics> any given family of graphs. For every integer <semantics>n≥|G|</semantics>, let <semantics>f(n,G|F)</semantics> denote the smallest integer k such that any edge coloring of <semantics>Kn</semantics> with at least k colors forces a copy of G in which each color class induces a member of <semantics>F</semantics>. Observe that in anti-Ramsey problems, each color class is a single edge, i.e., <semantics>F=K2</semantics>. Among the many results introduced in this paper, we mention the following. (1) For every graph G, there exists a constant <semantics>c=c(G)</semantics> such that in any edge coloring of <semantics>Kn</semantics> with at least <semantics>cn</semantics> colors there is a copy of G in which every vertex v is incident with an edge whose color appears only once among all edges incident with v. (2) In sharp contrast to the above result we prove that if <semantics>F</semantics> is the class of all odd graphs (having vertices with odd degrees only) then <semantics>f(n,Kk|F)=(1+o(1))<mspace width="0.166667em"></mspace>ex(n,K⌈k/2⌉)</semantics>, which is quadratic for <semantics>k≥5</semantics>. (3) We exactly determine <semantics>f(n,G|F)</semantics> for small graphs when <semantics>F</semantics> belongs to several families representing various odd/even coloring constraints.