Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles
Maria Axenovich, John L. Goldwasser, Ryan Hansen, Bernard Lidický, Ryan R. Martin, David Offner, John Talbot, Michael Young · Journal of Graph Theory · 2017
Abstract If G is a graph and is a set of subgraphs of G, then an edge‐coloring of G is called ‐polychromatic if every graph from gets all colors present in G. The ‐polychromatic number of G, denoted , is the largest number of colors such that G has an ‐polychromatic coloring. In this article, is determined exactly when G is a complete graph and is the family of all 1‐factors. In addition is found up to an additive constant term when G is a complete graph and is the family of all 2‐factors, or the family of all Hamiltonian cycles.