Title
Hadwiger Number and Chromatic Number for Near Regular Degree Sequences
Abbreviated Journal Title
J. Graph Theory
Keywords
Hadwiger number; chromatic number; graphic degree sequence; EVERY PLANAR MAP; Mathematics
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)=maxfh(G): G is an element of R[D]} and chi(D)=max{chi(G):G is an element of R[D]}, where h(G) and chi(G) are Hadwiger number and chromatic number of a graph G, respectively. Hadwiger's Conjecture implies that h(D) > =chi(D). In this paper, we establish the above inequality for near regular degree sequences. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 64: 175-183. 2010
Journal Title
Journal of Graph Theory
Volume
64
Issue/Number
3
Publication Date
1-1-2010
Document Type
Article
DOI Link
Language
English
First Page
175
Last Page
183
WOS Identifier
ISSN
0364-9024
Recommended Citation
"Hadwiger Number and Chromatic Number for Near Regular Degree Sequences" (2010). Faculty Bibliography 2010s. 702.
https://stars.library.ucf.edu/facultybib2010/702
Comments
Authors: contact us about adding a copy of your work at STARS@ucf.edu