Axenovich, M;
Goldwasser, J;
Hansen, R;
Lidický, B;
Martin, RR;
Offner, D;
Talbot, J;
(2018)
Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles.
Journal of Graph Theory
, 87
(4)
pp. 660-671.
10.1002/jgt.22180.
Preview |
Text
Poly1HC2.pdf - Accepted Version Download (288kB) | Preview |
Abstract
If G is a graph and math formula is a set of subgraphs of G, then an edge-coloring of G is called H-polychromatic if every graph from math formula gets all colors present in G. The H-polychromatic number of G, denoted poly_H(G), is the largest number of colors such that G has an H-polychromatic coloring. In this article, poly_H(G) is determined exactly when G 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 G is a complete graph and H is the family of all 2-factors, or the family of all Hamiltonian cycles.
| Type: | Article |
|---|---|
| Title: | Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1002/jgt.22180 |
| Publisher version: | http://dx.doi.org/10.1002/jgt.22180 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | 1-factor, 2-factor, hamiltonian cycle, polychromatic coloring |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/1573235 |
Archive Staff Only
 |
View Item |
