𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hadwiger number and chromatic number for near regular degree sequences

✍ Scribed by Neil Robertson; Zi-Xia Song

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
105 KB
Volume
64
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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. J Graph Theory 64: 175–183, 2010

📜 SIMILAR VOLUMES

Total chromatic number of regular graphs
Total chromatic number of regular graphs of odd order and high degree
✍ K.H. Chew 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 695 KB

The total chromatic number XT(G) of a graph G is the least number of colours needed to colour the edges and vertices of G so that no incident or adjacent elements receive the same colour. This paper shows that if G is odd order and regular of degree d > [(&? -1)/6]1 V(G)/, then a necessary and suffi

Degree sequence conditions for equal edg
Degree sequence conditions for equal edge-connectivity and minimum degree, depending on the clique number
✍ Lutz Volkmann 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 87 KB

## Abstract Using the well‐known Theorem of Turán, we present in this paper degree sequence conditions for the equality of edge‐connectivity and minimum degree, depending on the clique number of a graph. Different examples will show that these conditions are best possible and independent of all the