Originator: Csaba Biró (presented by Sogol Jahanbekan - REGS 2010)
Definitions: Let Q(n,c) denote the minimum of ω(G) over all n-vertex graphs with χ(G)=c, where χ(G) is the chromatic number of G and ω(G) is the maximum size of a clique in G.
Background: It is well known that for every natural number j there is a triangle-free graph having chromatic number at least j. The number of vertices needed grows quadratically with j. When the chromatic number is fairly close to the number of vertices, large cliques must occur. Another way to study this is to ask for the maximum difference between χ(G) and ω(G) when G has n vertices.
Conjecture (Biró [B]): Q(n,n-k)=n-⌊3k/2⌋ for sufficiently large n.
Comments: It is immediate that Q(n,n)=n, Q(n,n-1)=n-1, and Q(n,n-2)=n-3. Biró [B] proved that Q(n,n-3)=n-4. Thus the conjecture is proved for k≤ 3. In REGS, Jahanbekan and West observed that Q(n,n-k) is at most the conjectured value whenever n≥⌈5k/2⌉ and conjecture that this threshold on n is both sufficient and necessary for equality. A computer search by Kolb gave support to this conjecture by proving Q(9,5)=4.
The construction for the upper bound begins with the complement of rC5 when k=2r and with the complement of (r-1)C5+P3 when k=2r-1. Adding a dominating vertex increases the number of vertices, the chromatic number, and the clique number each by 1.
References:
[B] C. Biró, Large Cliques in Graphs with High Chromatic Number,
preprint.