The typical structure of Gallai colorings and their extremal graphs

Research output: Contribution to journalArticlepeer-review

Abstract

An edge coloring of a graph G is a Gallai coloring if it contains no rainbow triangle. We show that the number of Gallai r-colorings of Kn is ((r 2) + o(1))2(n 2). This result indicates that almost all Gallai r-colorings of Kn use only 2 colors. We also study the extremal behavior of Gallai r-colorings among all n-vertex graphs. We prove that the complete graph Kn admits the largest number of Gallai 3-colorings among all n-vertex graphs when n is sufficiently large, while for r ≥ 4, it is the complete bipartite graph K[n/2],[n/2]. Our main approach is based on the hypergraph container method, developed independently by Balogh, Morris, and Samotij as well as by Saxton and Thomason, together with some stability results.

Original languageEnglish (US)
Pages (from-to)2416-2443
Number of pages28
JournalSIAM Journal on Discrete Mathematics
Volume33
Issue number4
DOIs
StatePublished - 2019

Keywords

  • Container method
  • Extremal graph
  • Gallai coloring

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'The typical structure of Gallai colorings and their extremal graphs'. Together they form a unique fingerprint.

Cite this