Abstract
For every positive integer $k$, we consider a zero-one linear program describing the following optimization problem: maximize the number of nodes in a clique of an $n$-vertex graph whose chromatic number does not exceed k.
Although k is a trivial solution for this problem, we show that any cutting-plane proof certifying that no such graph can have a clique on more than $rk$ vertices must generate an exponential in $\min\{k,n/rk\}^{1/4}$ number of inequalities. We allow Gomory-Chvatal cuts and even the more powerful split cuts.
This extends the results of Pudlak [J.~Symb. Log. 62:3 (1997) 981--998] and Dash [Math. of Operations Research 30:3 (2005) 678--700; Oper. Res. Lett. 38:2 (2010), 109--114] who proved exponential lower bounds for the case when $k=n^{2/3}$ and $r=1$.