  A colored graph is a complete graph in which a color has been assigned to
each edge, and a colorful cycle is a cycle in which each edge has a different
color. We first show that a colored graph lacks colorful cycles iff it is
Gallai, i.e., lacks colorful triangles. We then show that, under the operation
$m\circ n\equiv m+n-2$, the omitted lengths of colorful cycles in a colored
graph form a monoid isomorphic to a submonoid of the natural numbers which
contains all integers past some point. We prove that several but not all such
monoids are realized.
  We then characterize exact Gallai graphs, i.e., graphs in which every
triangle has edges of exactly two colors. We show that these are precisely the
graphs which can be iteratively built up from three simple colored graphs,
having $2$, $4$, and $5$ vertices, respectively. We then characterize in two
different ways the monochromes, i.e., the connected components of maximal
monochromatic subgraphs, of exact Gallai graphs. The first characterization is
in terms of their reduced form, a notion which hinges on the important idea of
a full homomorphism. The second characterization is by means of a homomorphism
duality.
