The chromatic gap and its extremes

The chromatic gap is the difference between the chromatic number and the clique number of a graph. Here we investigate gap(n), the maximum chromatic gap over graphs on n vertices. Can the extremal graphs be explored? While computational problems related to the chromatic gap are hopeless, an interplay between Ramsey-theory and matching theory leads to a simple and (almost) exact formula for gap(n) in terms of Ramsey-numbers. For our purposes it is more convenient to work with the covering gap, the difference between the clique cover number and stability number of a graph and this is what we call the gap of a graph. Notice that the well-studied family of perfect graphs are the graphs whose induced subgraphs have gap zero. The maximum of the (covering) gap and the chromatic gap running on all induced subgraphs will be called perfectness gap.Using α(G) for the cardinality of a largest stable (independent) set of a graph G, we define where the minimum is taken over triangle-free graphs on n vertices. It is easy to observe that α(n) is essentially an inverse Ramsey function, defined by the relation R(3,α(n))⩽n