On colorings avoiding a rainbow cycle and a fixed monochromatic subgraph

Maria Axenovich ; JiHyeok Choi

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

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 Jamison and West, 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 $maxR(n, G,H)$. For graphs $H$ which can not be vertex-partitioned into at most two induced forests, $maxR(n, G,H)$ has been determined asymptotically. Determining $maxR(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 $maxR(n, G, C_k)$ is determined for all graphs $G$ whose edges do not induce a star.

Détail

DOI : 10.37236/303

Classification : 05C15, 05C55