We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles.
- Authors
Axenovich, Maria; Goldwasser, John; Hansen, Ryan; Lidický, Bernard; Martin, Ryan R.; Offner, David; Talbot, John; Young, Michael
- Abstract
Abstract: If <italic>G</italic> is a graph and H is a set of subgraphs of <italic>G</italic>, then an edge‐coloring of <italic>G</italic> is called H‐polychromatic if every graph from H gets all colors present in <italic>G</italic>. The H‐polychromatic number of <italic>G</italic>, denoted poly H ( G ), is the largest number of colors such that <italic>G</italic> has an H‐polychromatic coloring. In this article, poly H ( G ) is determined exactly when <italic>G</italic> is a complete graph and H is the family of all 1‐factors. In addition poly H ( G ) is found up to an additive constant term when <italic>G</italic> is a complete graph and H is the family of all 2‐factors, or the family of all Hamiltonian cycles.
- Subjects
GRAPH coloring; HAMILTONIAN graph theory; HYPERCUBES; SUBGRAPHS; GEOMETRIC vertices
- Publication
Journal of Graph Theory, 2018, Vol 87, Issue 4, p660
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22180