The Typical Structure of Gallai Colorings and Their Extremal Graphs
SIAM Journal on Discrete Mathematics · 2019-01 · 33 (4) · 2416-2443
DOI: 10.1137/19m1253344 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 05.12.2019. Verfasst von József Balogh und 1 weiteren Autor:innen. Die Arbeit wurde bisher 16-mal zitiert (Crossref) und nennt 25 Literaturangaben. Gefördert von: National Science Foundation, Beckman Institute for Advanced Science and Technology, University of Illinois, Urbana-Champaign.
Abstract (Originalsprache)
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 $(\binom{r}{2}+o(1))2^{\binom{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\geq 4$, it is the complete bipartite graph $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$. 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.
Förderung
- National Science Foundation
- Beckman Institute for Advanced Science and Technology, University of Illinois, Urbana-Champaign
Zitieren
APA
Balogh, J., & Li, L. (2019). The Typical Structure of Gallai Colorings and Their Extremal Graphs. SIAM Journal on Discrete Mathematics, 33(4), 2416-2443. https://doi.org/10.1137/19m1253344
Vancouver
Balogh J, Li L. The Typical Structure of Gallai Colorings and Their Extremal Graphs. SIAM Journal on Discrete Mathematics. 2019;33(4):2416-2443. doi:10.1137/19m1253344
BibTeX
@article{Balogh2019,
author = {Balogh, József and Li, Lina},
title = {The Typical Structure of Gallai Colorings and Their Extremal Graphs},
journal = {SIAM Journal on Discrete Mathematics},
year = {2019},
volume = {33},
number = {4},
pages = {2416--2443},
doi = {10.1137/19m1253344}
}
EUVIMED