Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles

Abstract

<p>If G is a graph and H is a set of subgraphs of G, then an edge-coloring of G is called H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polychromatic number of G, denoted polyH(G), is the largest number of colors in an H-polychromatic coloring. In this paper, polyH(G) is determined exactly when G is a complete graph and H is the family of all 1-factors. In addition polyH(G) is found up to an additive constant term when G is a complete graph and H is the family of all 2-factors, or the family of all Hamiltonian cycles.</p>