Hadwiger Number and Chromatic Number for Near Regular Degree Sequences

    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