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.