| Popis: |
For every positive integer l, 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 l. Although l 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 rl vertices must generate an exponential in minfl, n=rlg 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 l= n 2=3 and r= 1. |
Full Text from ScienceDirect