zbMATH — the first resource for mathematics

Lower bounds for the clique and the chromatic numbers of a graph. (English) Zbl 0535.05029
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.
Reviewer: A.J.Schwenk

05C15 Coloring of graphs and hypergraphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C99 Graph theory
PDF BibTeX Cite
Full Text: DOI
[1] Bondy, J.A., Bounds for the chromatic number of a graph, J. combin. theory, 7, 96-98, (1969) · Zbl 0182.57802
[2] Edwards, C.S., The largest vertex degree sum for a triangle in a graph, Bull. London math. soc., 9, 203-208, (1977) · Zbl 0357.05058
[3] Elphick, C.H., School timetabling and graph colouring, () · Zbl 0475.90045
[4] Erdös, P.; Bollobás, B., On the graph theorem of turan (in Hungarian), (), 21, 295-296, (1970), For a proof in English of this theorem of Erdös, see
[5] Hoffmann, A.J., On eigenvalues and colourings of graphs, (), 79-91
[6] Myers, B.R.; Liu, R., A lower bound on the chromatic number of a graph, Networks, 1, 273-277, (1972) · Zbl 0233.05105
[7] Schwenk, A.J., Computing the characteristic polynomial of a graph, (), 247-261
[8] Schwenk, A.J.; Wilson, R.J., Eigenvalues of graphs, (), 307-336
[9] Tutte, W.T.; Descartes, B., A three colour problem, Eureka, Solution, (March 1948)
[10] Waller, D.A., Eigenvalues of graphs and operations, Proc. british combinatorial conference, 177-183, (1973)
[11] Welsh, D.J.A.; Powell, M.B., An upper bound for the chromatic number of a graph and its application to timetabling problems, Comput. J., 10, 85-86, (1967) · Zbl 0147.15206
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.