id: 05814475
dt: j
an: 05814475
au: Robertson, Neil; Song, Zi-Xia
ti: Hadwiger number and chromatic number for near regular degree sequences.
so: J. Graph Theory 64, No. 3, 175-183 (2010).
py: 2010
pu: John Wiley \& Sons, New York, NY
la: EN
cc: 
ut: Hadwiger number; chromatic number; graphic degree sequence
ci: 
li: doi:10.1002/jgt.20447
ab: Summary: We consider a problem related to Hadwiger’s Conjecture. Let
    $D=(d_{1}, d_{2}, \dots , d_n)$ be a graphic sequence with $0 \leq
    d_{1} \leq d_{2} \leq \cdots \leq d_n \leq n - 1$. Any simple graph $G$
    with $D$ as 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\in R[D]\}$ and $χ(D)=\max \{χ(G): G\in R[D]\}$, where
    $h(G)$ and $χ(G)$ are the Hadwiger number and the chromatic number of
    a graph $G$, respectively. Hadwiger’s conjecture implies that $h(D)
    \geq χ(D)$. In this paper, we establish the above inequality for near
    regular degree sequences.
rv: