Colored graphs without colorful cycles (Q949751)

A cycle in a complete graph with coloured edges is called colourful if each of its edges has a different colour (such a subgraphs are sometimes called rainbow as well). It is shown that complete graphs with coloured edges do not have colourful cycles if and only if they are so-called Gallai graphs, i.e. graphs that do not possess colourful triangles. It is shown that the ommited edges of colourful cycles with the operation \(m\circ n = m+n-2\) form a monoid. The authors provide a characterisation of Gallai graphs and two characterization of the connected components of maximal monochromatic subgraphs of exact Gallai graphs. The characterizations of maximal monochromatic subgraphs are given in terms of full homomorphism and homomorphisms duality.