Improved bounds for the chromatic number of a graph

After giving a new proof of a well-known theorem of Dirac on critical graphs, we discuss the elegant upper bounds of Matula and Szekeres-Wilf which follow from it. In order to improve these bounds, we consider the following fundamental coloring problem: given an edge-cut (V1, V2) in a graph G, together with colorings of )V1* and )V2*, what is the least number of colors in a coloring of G which respects the colorings of )V1* and )V2*? We give a constructive optimal solution of this problem, and use it to derive a new upper bound for the chromatic number of a graph. As easy corollaries, we obtain several interesting bounds which also appear to be new, as well as classical bounds of Dirac and Ore, and the above mentioned bounds of Matula and Szekeres-Wilf. We conclude by considering two algorithms suggested by our results. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 217225, 2004