Lower bounds for the clique and the chromatic numbers of a graph.

*(English)*Zbl 0535.05029Because 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

##### MSC:

05C15 | Coloring of graphs and hypergraphs |

05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |

05C99 | Graph theory |

PDF
BibTeX
Cite

\textit{C. S. Edwards} and \textit{C. H. Elphick}, Discrete Appl. Math. 5, 51--64 (1983; Zbl 0535.05029)

Full Text:
DOI

##### References:

[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.