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 α(. n). =. min. α(. G) 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<. R(3, α(. n). +. 1). Our main result is that gap(. n). =. ?. n/2?. -. α(. n), possibly with the exception of small intervals (of length at most 15) around the Ramsey-numbers. R(3,. m), where the error is at most 3.The central notions in our investigations are the gap-critical and the gap-extremal graphs. A graph G is gap-critical if for every proper induced subgraph H?G, gap(H)展开▼
机译：的。色差是图形的色数和团数之间的差。在这里，我们研究了gap（.n），即图上的最大色差。 n个顶点。可以探索极值图吗？尽管与色差相关的计算问题是绝望的，但拉姆齐理论与匹配理论之间的相互作用导致了关于拉姆齐数的gap（.n）的简单（几乎）精确公式。为了我们的目的，与之合作更方便。覆盖间隙，即图形的集团覆盖数和稳定性数之间的差，这就是我们所说的。图的间隙。请注意，经过充分研究的理想图族是其诱导子图的间隙为零的图。在所有诱导子图上运行的（覆盖）间隙和色差的最大值将被调用。完美间隙：使用α（.G）表示图的最大稳定（独立）集的基数。 G，我们定义α（。n）。 =。分钟α（。G）的最小值取于无三角形图上。 n个顶点。容易观察到，α（.n）本质上是反拉姆西函数，由该关系定义。 R（3，α（.n））。 ≤。 n <。 R（3，α（。n）。+。1）。我们的主要结果是该差距（。n）。 =。 ？ n / 2？ - α（.n），可能是Ramsey数附近的小间隔（长度最大为15）除外。 R（3，.m），误差最大为3。在我们的研究中，中心概念是间隙临界图和间隙极值图。如果对于每个适当的诱导子图H？G，图G都是间隙临界的，则gap（H）展开▼
