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
Hoffman  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.
Graph coloring problems arise in the scheduling of exams for university courses ,
the scheduling of municipal services , the testing of computer circuits , 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 , .•. ,
and offers 7 courses
, ••• , C7.
Each student is registered in a subset of the as indicated in the following
2000 Mathematics Subject Classifications. Primary 05C15, 05C85, 15A18, 90C22.
2001 American Mathematical Society