MATH Seminar
| Title: The number of Gallai colorings |
|---|
| Seminar: Combinatorics |
| Speaker: Jie Han of University of Rhode Island |
| Contact: Dwight Duffus, dwightduffus@emory.edu |
| Date: 2019-01-18 at 4:00PM |
| Venue: MSC W301 |
| Download Flyer |
| Abstract: 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