Colored graphs without colorful cycles

DOI10.1007/S00493-007-2224-6zbMATH Open1174.05041arXiv1509.05621OpenAlexW2036460087MaRDI QIDQ949751FDOQ949751

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

Publication date: 21 October 2008

Published in: Combinatorica (Search for Journal in Brave)

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.

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

zbMATH Keywords

homomorphismmonoidrainbow colouringGallai graphcolourful cycle

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Transitiv orientierbare Graphen
• Edge colorings of complete graphs without tricolored triangles
• On classes of relations and graphs determined by subobjects and factorobjects
• Edge-colored complete graphs with precisely colored subgraphs
• Lambda composition
• On lengths of rainbow cycles

Cited In (11)

• Title not available (Why is that?)
• Rainbow generalizations of Ramsey theory: A survey
• Periods in missing lengths of rainbow cycles
• Dualities in full homomorphisms
• Gallai colorings and domination in multipartite digraphs
• Extensions of Gallai-Ramsey results
• Complete edge-colored permutation graphs
• On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
• Connected colourings of complete graphs and hypergraphs
• Decomposing complete edge-chromatic graphs and hypergraphs. Revisited
• A decomposition of Gallai multigraphs

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)