Discrete Mathematics and Optimization Seminar
Friday, Nov. 5th, 2010
MC 320, 4:00 PM
The chromatic gap and its extremes
András Sebő
CNRS, Laboratoire G-SCOP
Abstract: How big can the difference between the chromatic number and clique number be in a graph on at most n vertices? Can the extremal graphs be explored? While computational problems related to the chromatic gap of a graph are hopeless, an interplay between Ramsey graphs and matchings leads to a simple and (almost) exact formula for the maximum of this difference for graphs on at most n vertices in terms of Ramsey numbers. As a consequence, the Ramsey graphs for R(3; :) have high matchability and connectivity properties.

Joint work with Nicolas Trotignon and András Gyárfás