The chromatic gap and its extremes (Q713979): Difference between revisions

The \textit{chromatic gap} is the difference between the chromatic number and the clique number of a graph. The authors investigate \textbf{\(gap(n)\)}, which is the maximum chromatic gap over graphs of order \(n\), and \(s(t)\), which is the smallest order of a graph with gap \(t\). The approach is unique in that the results will be given in terms of Ramsey numbers. The main result is that \(gap(n) = \lceil n/2 \rceil - \alpha(n)\), where \(\alpha(n)\) (an inverse Ramsey function) is defined by the inequality \(R(3, \alpha(n)) \leq n < R(3, \alpha(n) + 1)\). They also show that \(s(t) = 2t + \Theta \left(\sqrt{t \log t}\right)\). Similar results are also obtained for the functions \(gap_2(n)\) and \(s_2(t)\) which apply to triangle-free graphs, and conjecture that \(gap(n) = gap_2(n)\) and \(s(t) = s_2(t)\) for all \(n\) and \(t\). The exact values for \(s_2(t)\) for \(1 \leq t \leq 11\) were determined: specifically they are \(5, 10, 13, 17, 21, 25, 29, 31, 33, 35, 39\).