Hadwiger number and chromatic number for near regular degree sequences

We consider a problem related to Hadwiger's Conjecture. Let D =( d 1 , d 2 , …, d n ) be a graphic sequence with 0⩽ d 1 ⩽ d 2 ⩽···⩽ d n ⩽ n −1. Any simple graph G with D its degree sequence is called a realization of D . Let R [ D ] denote the set of all realizations of D . Define h ( D )=max{ h ( G ): G ∈ R [ D ]} and χ( D )=max{χ( G ): G ∈ R [ D ]}, where h ( G ) and χ( G ) are Hadwiger number and chromatic number of a graph G , respectively. Hadwiger's Conjecture implies that h ( D )⩾χ( D ). In this paper, we establish the above inequality for near regular degree sequences. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 175–183, 2010