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.