Extremal graphs for the number of k-colourings


Meeting Time: Oct. 13, 2009, 2:00-2:50pm

Abstract: Po-shen Loh, Oleg Pikhurko, and Benny Sudakov recently made a breakthrough in the problem, asked by Linial and Wilf in the 80's, of determining the graph G, on n vertices with m edges, having the greatest number of proper colorings to \{1,2,...q\}. Their approach uses Szemeredi's regularity lemma, to which I will provide a brief introduction.