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