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 [email protected]

    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
     

    Accessibility Statement

    This item was created or digitized prior to April 24, 2027, or is a reproduction of legacy media created before that date. It is preserved in its original, unmodified state specifically for research, reference, or historical recordkeeping. In accordance with the ADA Title II Final Rule, the University Libraries provides accessible versions of archival materials upon request. To request an accommodation for this item, please submit an accessibility request form.