Hadwiger number and chromatic number for near regular degree sequences |
| |
Authors: | Neil Robertson Zi‐Xia Song |
| |
Affiliation: | 1. Department of Mathematics, The Ohio State University, Columbus, OH 43210;2. Department of Mathematics, University of Central Florida, Orlando, FL 32816 |
| |
Abstract: | We consider a problem related to Hadwiger's Conjecture. Let D=(d1, d2, …, dn) be a graphic sequence with 0?d1?d2?···?dn?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 |
| |
Keywords: | Hadwiger number chromatic number graphic degree sequence |
|
|