A colorful cycle in a vertex-colored graph is a graph cycle whose vertices have distinct colors.
If the graph has
colors and the cycle has length , then the cycle contains exactly one vertex of each color.
For vertex-colored graphs, Angles d'Auriac et al. (2016) call a subgraphtropical
if it contains every color, rainbow if it contains
no color more than once, and colorful if it
is both tropical and rainbow. Thus a colorful cycle in a graph with colors is a cycle that is both tropical
and rainbow.
The terminology should not be confused with the use of "rainbow cycle" or "colorful cycle" in edge-colored graph theory, where the colors are
assigned to edges rather than vertices (Alexeev 2005, Ball et al. 2007).
Alexeev, B. "On Lengths of Rainbow Cycles." 22 Jul 2005. https://arxiv.org/abs/math/0507456.Alon,
N.; Yuster, R.; and Zwick, U. "Color-Coding." J. ACM42,
844-856, 1995. https://doi.org/10.1145/210332.210337.Angles
d'Auriac, J.-C.; Cohen, N.; El Maftouhi, A.; Harutyunyan, A.; Legay, S.; and Manoussakis,
G. "Connected Tropical Subgraphs in Vertex-Colored Graphs." Disc. Math.
Theor. Comput. Sci.17, 31-42, 2016. https://doi.org/10.46298/dmtcs.2151.Ball,
G.; Pultr, A.; and Vojtechovský, P. "Colored Graphs without Colorful
Cycles." Combinatorica27, 407-427, 2007. https://doi.org/10.1007/s00493-007-2224-6.Panolan,
F. and Zehavi, M. "Parameterized Algorithms for List K-Cycle." 36th
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer
Science. Leibniz International Proceedings in Informatics 65, Article
22, 2016. https://doi.org/10.4230/LIPIcs.FSTTCS.2016.22.
colors and the cycle has length 
, then the cycle contains exactly one vertex of each color.
colors is a cycle that is both tropical
and rainbow.
