|
|
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
|
|
|
|