Inefficient Bounds can be Efficient in some cases

Nico also points out that bounds which aren’t efficiently computable in general can be computed efficiently in special cases. For instance, the chromatic number is not generally efficiently computable – but is for bipartite graphs, perfect graphs, etc.

In the case of the difficult graph J?`FBo{fdb?, the chromatic number is 3. Since (independence number)(chromatic number) is always at least the order of the graph, since the order is 11, and independence number is integral, this implies that independence number is at least 4, which exactly predicts its true value.

So… maybe graph J?`FBo{fdb? belongs to some class of graphs where chromatic number can be computed efficiently? This would solve our problem.



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