Title

Hadwiger Number And Chromatic Number For Near Regular Degree Sequences

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) = 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.

Publication Date

1-1-2010

Publication Title

Journal of Graph Theory

Volume

64

Issue

3

Number of Pages

175-183

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1002/jgt.20447

Socpus ID

77954342296 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/77954342296

This document is currently not available here.

Share

COinS