Lower bounds for the clique and the chromatic numbers of a graph (Q790829)

Because of the difficulty in calculating the chromatic number \(\chi\) (G) and the clique number cl(G), algorithms are generally of the branch and variety. This article presents the history of bounds on these two parameters and makes some valuable improvements. In particular, a bound of Myers and Liu is improved to read \(cl(G)\geq n/[n-(2m/n)(1+c^ 2\!_ v)^{0.5}]\) where \(c_ v\) is the vertex degree coefficient of variation in G. For \(\lambda_ 1\) denoting the largest eigenvalue of G, they find \(\chi(G)\geq n/(n-\lambda_ 1)\) and \(cl(G)>n/(n-\lambda_ 1)-1/3.\) Other bounds that are not easily described are developed. They conclude with a constructive lower bound for cl(G) that is always at least as good as the Bondy bound. They tested the effectiveness of the various bounds on random graphs with 20 and 50 vertices. This last mentioned constructive lower bound was usually the largest, suggesting that it is generally the best known bound to date.