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