Shearer’s Bounds for Triangle-free Graphs

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:

  1. \alpha\geq \dfrac{n(\bar{d}\ln \bar{d}-\bar{d}+1)}{(\bar{d}-1)^2}, where \bar{d} is the average degree of the vertices of the graph.
  2. \alpha \geq \sum_{i=1}^{n}f(d_i), where f(0)=1, f(d)=\dfrac{1+(d^2-d)f(d-1)}{(d^2+1)d}, and 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.


Leave a Reply

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

You are commenting using your 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