✦ LIBER ✦

Degrees and choice numbers

✍ Scribed by Noga Alon

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 74 KB
Volume: 16
Category: Article
ISSN: 1042-9832
DOI: 10.1002/1098-2418(200007)16:4<364::aid-rsa5>3.0.co;2-0

No coin nor oath required. For personal study only.

✦ Synopsis

The choice number ch G of a graph G = V E is the minimum number k such that for every assignment of a list S v of at least k colors to each vertex v ∈ V , there is a proper vertex coloring of G assigning to each vertex v a color from its list S v . We prove that if the minimum degree of G is d, then its choice number is at least 1 2 -o 1 log 2 d, where the o 1 -term tends to zero as d tends to infinity. This is tight up to a constant factor of 2 + o 1 , improves an estimate established by the author, and settles a problem raised by him and Krivelevich.

📜 SIMILAR VOLUMES

Choice number and energy of graphs

✍ Saieed Akbari; Ebrahim Ghorbani 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 87 KB

Chromatic number, girth and maximal degr

Chromatic number, girth and maximal degree

✍ Béla Bollobás 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 544 KB

It is proved that for every k a4 there is a A(k) such that for eve:y g there is a graph G with maximal degree at most A(k), chromatic number at least k and girth at least g. In fact, for a fixed k, the restriction of the maximal degree to A(k) does not seem to slow down the ptiih of the maximal girt

Hadwiger number and chromatic number for

Hadwiger number and chromatic number for near regular degree sequences

✍ Neil Robertson; Zi-Xia Song 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## 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__] denot

The public choice of differing degrees o

The public choice of differing degrees of tax progressivity

✍ Kenneth V. Greene 📂 Article 📅 1986 🏛 Springer US 🌐 English ⚖ 892 KB

The number of three-choice polygons

✍ A. Conway; A.J. Guttmann; M. Delest 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 763 KB

polynomial time enumeration method for the three-choice polygon model in two dimensions is given together with numerical analysis of the enumerated series and an argument supporting the asymptotic behaviour of the number of imperfect staircase polygons.

Binding number and minimum degree for k-

Binding number and minimum degree for k-factors

✍ Norihide Tokushige 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 282 KB