2018/05/17 by Bastos, Josefran de Oliveira, Benevides, Fabricio Siqueira, Mota, Guilherme Oliveira +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1805.06805
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 the number of Gallai colorings of Kn with at most three colors is at most 7(n+1)*2n choose 2, which improves the best known upper bound of (3)/(2) * (n-1)! * 2(n-1) choose 2 in [Discrete Mathematics, 2017].