Optimization Online


Strengthening weak sandwich theorems in the presence of inconnectivity

Miklos Ujvari(ujvarim***at***cs.elte.hu)

Abstract: 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.


Category 1: Combinatorial Optimization

Citation: unpublished: ORR report 2010-1, www.cs.elte.hu/opres/orr

Download: [PDF]

Entry Submitted: 02/17/2010
Entry Accepted: 02/17/2010
Entry Last Modified: 02/17/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society