MATH Seminar

Title: Domination in 3-edge-colored complete graphs
Seminar: Combinatorics
Speaker: Daniel Kral of The University of Warwick
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2013-04-19 at 4:00PM
Venue: MSC W303
Download Flyer
Abstract: Erdos, Faudree, Gould, Gyarfas, Rousseau and Schelp proved that for every complete graph of order $n$ with edges colored with three colors, there exist a set $X$ of 22 vertices and a color $c$ such that the number of vertices in $X$ or joined to a vertex of $X$ by an edge of color $c$ is at least $2n/3$. They also conjectured that the bound of 22 can be lowered to 3. We improve the bound to 4. The talk is based on joint work with Chun-Hung Liu, Jean-Sebastien Sereni, Peter Whalen and Zelealem Yilma.