The chromatic gap and its extremes

Abstract

The {\em 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.

41 pages; Cahiers Leibniz No 184, https://consult-cahiersleibniz.g-scop.grenoble-inp.fr/apps/WebObjects/CahiersLeibniz/

References in corpus (3)

• The chromatic gap and its extremes
• Large cliques in graphs with high chromatic number
• Large chromatic number and Ramsey graphs

Cited by in corpus (5)

• The chromatic gap and its extremes
• A Constructive Formalization of the Weak Perfect Graph Theorem
• Large chromatic number and Ramsey graphs
• On the Complexity of Maximum Clique Algorithms: usage of coloring heuristics leads to the 2^(n\5) algorithm running time lower bound
• Towards a constructive formalization of Perfect Graph Theorems