In the paper we consider degree, spectral, and semidefinite bounds on the stability and chromatic numbers of a graph: so-called weak sandwich theorems. We examine the additivity properties of the bounds (the sum of two graphs is their disjoint union), and as an application we tighten the bounds in the weak sandwich theorems, if the graph or its complementer is not connected.
Citation
unpublished: ORR report 2010-1, www.cs.elte.hu/opres/orr
Article
View Strengthening weak sandwich theorems in the presence of inconnectivity