New upper bounds for the chromatic number of a graph

We show that for any graph G, the chromatic number chi (G) less than or equal to Delta (2)(G) + 1, where Delta (2)(G) is the largest degree that a vertex nu can have subject to the condition that nu is adjacent to a vertex whose degree is at least as big as its own, Moreover, we show that the upper bound is best possible in the the following sense: If Delta (2)(G) greater than or equal to 3, then to determine whether chi (G) less than or equal to Delta (2)(G) is an NP-complete problem. (C) 2001 John Wiley & Sons, Inc.