Editing Graph coloring (section)

=== Lower bounds on the chromatic number ===
Several lower bounds for the chromatic bounds have been discovered over the years:

If ''G'' contains a [[clique (graph theory)|clique]] of size ''k'', then at least ''k'' colors are needed to color that clique; in other words, the chromatic number is at least the clique number:
: <math>\chi(G) \ge \omega(G).</math>

For [[perfect graph]]s this bound is tight. Finding cliques is known as the [[clique problem]].

'''Hoffman's bound:''' Let <math>W</math> be a real symmetric matrix such that <math> W_{i,j} = 0 </math> whenever <math>(i,j) </math> is not an edge in <math>G</math>. Define <math>\chi_W(G) = 1 - \tfrac{\lambda_{\max}(W)}{\lambda_{\min}(W)}</math>, where <math>\lambda_{\max}(W), \lambda_{\min}(W)</math> are the largest and smallest eigenvalues of <math>W</math>. Define <math display="inline"> \chi_H(G) = \max_W \chi_W(G)</math>, with <math>W</math> as above. Then:
: <math> \chi_H(G)\leq \chi(G).</math>

'''{{vanchor|Vector chromatic number}}:''' Let <math>W</math> be a positive semi-definite matrix such that <math> W_{i,j} \le -\tfrac{1}{k-1} </math> whenever <math>(i,j) </math> is an edge in <math>G</math>. Define <math>\chi_V(G)</math> to be the least k for which such a matrix <math>W</math> exists. Then
: <math> \chi_V(G)\leq \chi(G).</math>

'''[[Lovász number]]:''' The Lovász number of a complementary graph is also a lower bound on the chromatic number:
: <math> \vartheta(\bar{G}) \leq \chi(G).</math>

'''[[Fractional chromatic number]]:''' The fractional chromatic number of a graph is a lower bound on the chromatic number as well:
: <math> \chi_f(G) \leq \chi(G).</math>

These bounds are ordered as follows:
: <math> \chi_H(G) \leq \chi_V(G) \leq \vartheta(\bar{G}) \leq \chi_f(G) \leq \chi(G).</math>