De Klerk and Pasechnik (2002) introduced the bounds () for the stability number of a graph and conjectured exactness at order : . These bounds rely on the conic approximations by Parrilo (2000) for the copositive cone . A difficulty in the convergence analysis of is the bad behaviour of the cones under adding a zero row/column: when applied to a matrix not in this gives a matrix not in any , thereby showing strict inclusion for . We investigate the graphs with for : we algorithmically reduce testing exactness of to acritical graphs, we characterize critical graphs with exact, and we exhibit graphs for which exactness of is not preserved under adding an isolated node. This disproves a conjecture by Gvozdenovi'c and Laurent (2007) which, if true, would have implied the above conjecture by de Klerk and Pasechnik.

生成讲解博客的中文版本

生成AI智能校验的中文版本