New upper bounds for the chromatic number of a graph
Ladislav Stacho · Journal of Graph Theory · 2001
We show that for any graph G, the chromatic number χ(G) ≤ Δ2(G) + 1, where Δ2(G) is the largest degree that a vertex ν can have subject to the condition that ν 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 Δ2(G) ≥ 3, then to determine whether χ(G) ≤ Δ2(G) is an NP-complete problem. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 117–120, 2001