On colorings avoiding a rainbow cycle and a fixed monochromatic subgraph (Q2380463)

Summary: Let \(H\) and \(G\) be two graphs on fixed number of vertices. An edge coloring of a complete graph is called \((H,G)\)-good if there is no monochromatic copy of \(G\) and no rainbow (totally multicolored) copy of \(H\) in this coloring. As shown by \textit{R. E. Jamison} and \textit{D. B. West} [Graphs Comb. 20, No. 3, 333--339 (2004; Zbl 1053.05088)], an \((H, G)\)-good coloring of an arbitrarily large complete graph exists unless either \(G\) is a star or \(H\) is a forest. The largest number of colors in an \((H,G)\)-good coloring of \(K_n\) is denoted \(\max R(n,G,H)\). For graphs \(H\) which can not be vertex-partitioned into at most two induced forests, \(\max R(n,G,H)\) has been determined asymptotically. Determining \(\max R(n,G, H)\) is challenging for other graphs \(H\), in particular for bipartite graphs or even for cycles. This manuscript treats the case when \(H\) is a cycle. The value of \(\max R(n,G,C_k)\) is determined for all graphs \(G\) whose edges do not induce a star.