## 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 K_{n} is ((^{r} _{2}) + o(1))2(^{n} _{2}). This result indicates that almost all Gallai r-colorings of K_{n} 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 K_{n} 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 language | English (US) |
---|---|

Pages (from-to) | 2416-2443 |

Number of pages | 28 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 33 |

Issue number | 4 |

DOIs | |

State | Published - 2019 |

## Keywords

- Container method
- Extremal graph
- Gallai coloring

## ASJC Scopus subject areas

- General Mathematics