Monochromatic Graph Decompositions Inspired by Anti-Ramsey Theory and Parity Constraints

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 F any given family of graphs. For every integer n ≥ | G | , let f ( n , G | F ) denote the smallest integer k such that any edge coloring of K n with at least k colors forces a copy of G in which each color class induces a member of F . Observe that in anti-Ramsey problems, each color class is a single edge, i.e., F = { K 2 } . Among the many results introduced in this paper, we mention the following. (1) For every graph G , there exists a constant c = c ( G ) such that in any edge coloring of K n with at least c n 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 F is the class of all odd graphs (having vertices with odd degrees only) then f ( n , K k | F ) = ( 1 + o ( 1 ) ) ex ( n , K ⌈ k / 2 ⌉ ) , which is quadratic for k ≥ 5 . (3) We exactly determine f ( n , G | F ) for small graphs when F belongs to several families representing various odd/even coloring constraints.