quality:correction, structural:scholar_edition, stylistic:style_transfer
Lower bounds on the chromatic number

Several lower bounds for the chromatic bounds have been discovered over the years:

If G contains a 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:

For perfect graphs this bound is tight. Finding cliques is known as the clique problem.

Hoffman's bound: Let W {\displaystyle W} be a real symmetric matrix such that W i, j = 0 {\displaystyle W_{i,j}=0} whenever (i, j) {\displaystyle (i,j)} is not an edge in G {\displaystyle G}. Define χ W (G) = 1 − λ max (W) λ min (W) {\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}}, where λ max (W), λ min (W) {\displaystyle \lambda _{\max }(W),\lambda _{\min }(W)} are the largest and smallest eigenvalues of W {\displaystyle W}. Define χ H (G) = max W χ W (G) {\textstyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}, with W {\displaystyle W} as above. Then:

Vector chromatic number: Let W {\displaystyle W} be a positive semi-definite matrix such that W i, j ≤ − 1 k − 1 {\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}} whenever (i, j) {\displaystyle (i,j)} is an edge in G {\displaystyle G}. Define χ V (G) {\displaystyle \chi _{V}(G)} to be the least k for which such a matrix W {\displaystyle W} exists. Then

Lovász number: The Lovász number of a complementary graph is also a lower bound on the chromatic number:

Fractional chromatic number: The fractional chromatic number of a graph is a lower bound on the chromatic number as well:

These bounds are ordered as follows: