Lorentzen’s Fractional Edge Cover Upper Bound

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):

\alpha\leq 2\rho^*-\rho,

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

\alpha\leq 2\alpha^*+\mu-n,

where \alpha^* is the fractional independence number (a very good upper bound on its own), \mu 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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s