Title

Hadwiger Number and Chromatic Number for Near Regular Degree Sequences

Authors

Authors

N. Robertson;Z. X. Song

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

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

Language

English

First Page

175

Last Page

183

WOS Identifier

WOS:000278919700001

ISSN

0364-9024

Share

COinS