Premium
Hadwiger number and chromatic number for near regular degree sequences
Author(s) -
Robertson Neil,
Song ZiXia
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20447
Subject(s) - combinatorics , mathematics , conjecture , simple graph , degree (music) , graph , discrete mathematics , chromatic scale , physics , acoustics
Abstract 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