Degree sequences and chromatic numbers of graphs

Abstract

We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values Χ(G) of the function chromatic number completely cover a line segment [a, b] of positive integers. Thus for an arbitrary graphical sequence d, two invariants minΧ(d) := a and maxΧ(d) := b naturally arise. For a regular graphical sequence d = rn := (r, r,...,r) where r is the degree and n is the number of vertices, the exact values of a and b are found in all situations, except the case where n and r are both even and n < 2r.