Here are two more special bounds for the independence number of a graph not yet included in the current draft of the “alpha-bounds survey” due to James Shearer. The first is earlier (1982) and simpler-to-state, the second is a more recent (1991) improvement:

- , where is the average degree of the vertices of the graph.
- , where , latex d_i$ is the degree of the ith vertex.

The significance here, of course, is that it can be efficiently determined whether a graph is triangle-free (naively you only need to check each of the roughly n^3 triples of vertices), and the degrees, average degrees, and Shearer’s invariants can also be efficiently computed. So for this efficiently determinable class of graphs, Shearer gives new efficiently computable lower bounds for the independence number.

Advertisements