Gallai Multigraphs

2007/06/30 by Kyle Pula, Pula, Kyle
Mathematics · Social Sciences · #05C15 #05C55 #China's Ethnic Minorities and Relations #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C55

paper · pdf · doi:10.48550/arxiv.0707.0084

16 pages, 5 figures

arxiv created 2007/06/30 · openalex publication_date 2007/06/30 · arxiv updated 2009/12/01 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28

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.

Related

• Counting Gallai 3-colorings of complete graphs
• The typical structure of Gallai colorings and their extremal graphs
• Note on a generalization of Gallai-Ramsey numbers
• The number of Gallai k-colorings of complete graphs
• Gallai-Ramsey numbers for graphs with five vertices of chromatic number four