Colored graphs without colorful cycles

DOI10.1007/S00493-007-2224-6MaRDI QIDQ949751zbMATH OpenOpenAlexFDO

Authors Richard N. Ball, Petr Vojtěchovskí, A. Pultr

Publication date 21 October 2008

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.05621

zbMATH Keywords

colourful cycleGallai graphhomomorphismmonoidrainbow colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Abstract: 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 $mcircnequivm+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.

Review text

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.

Recommendations

• Gallai colorings of non-complete graphs
• Cycles avoiding a color in colorful graphs
• Edge-colored complete graphs containing no properly colored odd cycles
• Edge‐colored complete graphs without properly colored even cycles: A full characterization
• A decomposition of Gallai multigraphs

Cites work

• Edge colorings of complete graphs without tricolored triangles
• Edge-colored complete graphs with precisely colored subgraphs
• scientific article; zbMATH DE number 863494 (Why is no real title available?)
• Lambda composition
• On classes of relations and graphs determined by subobjects and factorobjects
• On lengths of rainbow cycles
• Transitiv orientierbare Graphen

Cited in

(12)

• Dualities in full homomorphisms
• A decomposition of Gallai multigraphs
• Complete edge-colored permutation graphs
• Extensions of Gallai-Ramsey results
• Periods in missing lengths of rainbow cycles
• Gallai colorings and domination in multipartite digraphs
• scientific article; zbMATH DE number 6750761 (Why is no real title available?)
• Connected colourings of complete graphs and hypergraphs
• Rainbow generalizations of Ramsey theory: A survey
• On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
• Not complementary connected and not CIS d-graphs form weakly monotone families
• Decomposing complete edge-chromatic graphs and hypergraphs. Revisited

This page was built for publication: Colored graphs without colorful cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q949751)