Tell me more ×  I am trying to find a good lower bound for
chromatic number of one family of graphs. I'm curious what are
the known lower bounds for chromatic number. There are two
obvious: $\chi(G) \geq \omega(G)$ and $\chi(G) \geq n /
\alpha(G)$. One can also employ fancy Lovasz theta-function.
Chromatic number of Kneser graph can be obtained by the means of
topological combinatorics (particularly, using Borsuk-Ulam
theorem). But it is not clear if this method is general enough.
So, what are the more or less general techniques for
lowerbounding chromatic number?  share|improve this question
Just one graph? Can't you just explicitly compute the chromatic
polynomial? –  Qiaochu Yuan Jul 29 '10 at 17:48 I'm sorry, one
family of graphs. Anyway, they are way too big. –  ilyaraz Jul
29 '10 at 18:15 The theta function can be found in polynomial
time, unlike the two other bounds you suggest. As Suresh
commented, it can be expressed as the solution of a semi-
definite program, and can therefore be found using linea