While reading Shrijver’s Combinatorial Optimization, I ran across the following interesting and efficiently computable upper bound for the independence number due to Lorentzen (1966):

,

where is the edge covering number, and is the fractional edge covering number. In terms of invariants that we’re already coded this becomes

,

where is the fractional independence number (a very good upper bound on its own), is the matching number, and *n* is the order of the graph.

Lorentzen’s bound is included in a technical report . While it is cited by Shrijver and Lovasz, among others, no pdf of this report seems to be available anywhere. That surprises me a little.

Advertisements