Polychromatic colorings of 1-regular and 2-regular subgraphs of complete graphs

Abstract

If $G$ is a graph and $\mathcal{H}$ is a set of subgraphs of $G$, we say that an edge-coloring of $G$ is $\mathcal{H}$-polychromatic if every graph from $\mathcal{H}$ gets all colors present in $G$ on its edges. The $\mathcal{H}$-polychromatic number of $G$, denoted ${\mathrm{poly}}_{\mathcal{H}}(G)$, is the largest number of colors in an $\mathcal{H}$-polychromatic coloring. In this paper we determine ${\mathrm{poly}}_{\mathcal{H}}(G)$ exactly when $G$ is a complete graph on $n$ vertices, $q$ is a fixed nonnegative integer, and $\mathcal{H}$ is one of three families: the family of all matchings spanning $n-q$ vertices, the family of all $2$-regular graphs spanning at least $n-q$ vertices, and the family of all cycles of length precisely $n-q$. There are connections with an extension of results on Ramsey numbers for cycles in a graph.

27 pages, 3 figures