The clique-number conjecture for graphs with chromatic number near the order

Let Q(n,r)Q(n,r) denote the minimum clique number among graphs on nn vertices with chromatic number rr. The clique-number conjecture. Let kk be a positive integer. If nn is sufficiently large, then

Q(n,nk)=n2k+k2 rounded up.Q(n,n-k)=n-2k+\frac{k}{2}\text{ rounded up}.

This conjecture was disproven, although the stated formula was later verified for k6k\leq 6.

Sources & referencesView supporting material

Primary source

Csaba Biró, “Large cliques in graphs with high chromatic number”, arXiv:1107.2630 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.