MATH Seminar

Title: The number of Gallai colorings
Seminar: Combinatorics
Speaker: Jie Han of University of Rhode Island
Contact: Dwight Duffus,
Date: 2019-01-18 at 4:00PM
Venue: MSC W301
Download Flyer
An edge coloring of the complete graph Kn is called a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle in which all three edges have distinct colors. Given a set of k colors and integer n, we are interested in the number of Gallai colorings of Kn with colors from the given set. In particular, we show that for k at most exponential in n, namely, k < 2^n/4300, almost all Gallai colorings use at most 2 colors. Interestingly, this statement fails for k > 2^n/2. This is joint work with Josefran O. Bastos and Fabricio S. Benevides (University of Ceara, Brazil).

See All Seminars