The chromatic gap and its extremes (Q713979): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:02, 5 March 2024
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
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
clique number
0 references
chromatic number
0 references
Ramsey numbers
0 references