TY - JOUR
T1 - The number of Gallai k-colorings of complete graphs
AU - Bastos, Josefran de Oliveira
AU - Benevides, Fabrício Siqueira
AU - Han, Jie
N1 - Publisher Copyright:
© 2020 Elsevier Inc.
PY - 2020/9
Y1 - 2020/9
N2 - An edge coloring of the n-vertex complete graph, Kn, is a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle whose edges are colored with three distinct colors. We prove that for n large and every k with k≤2n/4300, the number of Gallai colorings of Kn that use at most k given colors is ((k2)+on(1))2(n2). Our result is asymptotically best possible and implies that, for those k, almost all Gallai k-colorings use only two colors. However, this is not true for k≥2n/2.
AB - An edge coloring of the n-vertex complete graph, Kn, is a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle whose edges are colored with three distinct colors. We prove that for n large and every k with k≤2n/4300, the number of Gallai colorings of Kn that use at most k given colors is ((k2)+on(1))2(n2). Our result is asymptotically best possible and implies that, for those k, almost all Gallai k-colorings use only two colors. However, this is not true for k≥2n/2.
KW - Complete graphs
KW - Counting
KW - Gallai colorings
KW - Rainbow triangles
UR - http://www.scopus.com/inward/record.url?scp=85077378198&partnerID=8YFLogxK
U2 - 10.1016/j.jctb.2019.12.004
DO - 10.1016/j.jctb.2019.12.004
M3 - Article
AN - SCOPUS:85077378198
SN - 0095-8956
VL - 144
SP - 1
EP - 13
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
ER -