Contemporary Mathematics Volume 275, 2001 A Lower Bound for the Chromatic Number of a Graph Earl R. Barnes December 15, 2000 School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, Georgia 30332-0205 Abstract Hoffman [1] has given a lower bound on the chromatic number of a graph in terms of the extreme eigenvalues of the adjacency matrix of the graph. In this paper we give a sharper lower bound on the chromatic number. Our bound requires the solution of a semidefinite programming problem which depends on an extreme eigenvector of the adjacency matrix. We describe an efficient algorithm for solving this problem. 1 Introduction. Graph coloring problems arise in the scheduling of exams for university courses [2], the scheduling of municipal services [3], the testing of computer circuits [4], and in many other areas. We will give a small example of the exam scheduling problem to motivate our dicussion of the graph coloring problem. Imagine a small university which has 10 students s 1, .•. , s 10 , and offers 7 courses c1, ••• , C7. Each student is registered in a subset of the as indicated in the following table. 2000 Mathematics Subject Classifications. Primary 05C15, 05C85, 15A18, 90C22. © 2001 American Mathematical Society 3 http://dx.doi.org/10.1090/conm/275/04486
Previous Page Next Page