A decomposition of Gallai multigraphs

DOI10.7151/DMGT.1740zbMATH Open1290.05075arXiv0707.0084OpenAlexW2081586032MaRDI QIDQ2450129FDOQ2450129

Authors: Alexander Halperin, Colton Magnant, Kyle Pula 

Publication date: 16 May 2014

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: A complete edge-colored graph or multigraph is called Gallai if it lacks rainbow triangles. We give a construction of all finite Gallai multigraphs.

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

Recommendations

• The Typical Structure of Gallai Colorings and Their Extremal Graphs
• Colored graphs without colorful cycles
• Distribution of colors in Gallai colorings
• Gallai colorings of non-complete graphs
• Ramsey-type results for Gallai colorings

zbMATH Keywords

edge coloringGallai multigraph

Mathematics Subject Classification ID

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

Cites Work

• Transitiv orientierbare Graphen
• Rainbow generalizations of Ramsey theory: A survey
• On rainbow trees and cycles
• Ramsey-type results for Gallai colorings
• Edge colorings of complete graphs without tricolored triangles
• Extensions of Gallai-Ramsey results
• Title not available (Why is that?)
• Gallai-Ramsey numbers for cycles
• Colored graphs without colorful cycles
• On lengths of rainbow cycles
• Periods in missing lengths of rainbow cycles

Cited In (4)

• Density of Gallai multigraphs
• Rainbow tetrahedra in Cayley graphs
• Rainbow generalizations of Ramsey theory: A survey
• Colored graphs without colorful cycles

This page was built for publication: A decomposition of Gallai multigraphs

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