The chromatic gap and its extremes (Q713979)

From MaRDI portal
Revision as of 19:42, 5 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
The chromatic gap and its extremes
scientific article

    Statements

    The chromatic gap and its extremes (English)
    0 references
    0 references
    0 references
    0 references
    19 October 2012
    0 references
    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\).
    0 references
    0 references
    0 references
    0 references
    0 references
    clique number
    0 references
    chromatic number
    0 references
    Ramsey numbers
    0 references
    0 references
    0 references