𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Semidefinite bounds for the stability number of a graph via sums of squares of polynomials

✍ Scribed by Nebojša Gvozdenović; Monique Laurent

Publisher
Springer-Verlag
Year
2006
Tongue
English
Weight
419 KB
Volume
110
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Bounds for the harmonious chromatic numb
Bounds for the harmonious chromatic number of a graph
✍ I. Krasikov; Y. Roditty 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 231 KB 👁 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph given by Zhikang Lu and by C. McDiarmid and Luo Xinhua, independently (__Journal of Graph Theory__, 1991, pp. 345–347 and 629–636) and the lower bound given by D. G. Beane, N. L. Biggs, and B. J. Wilson (__Journal of Graph T

Improved bounds for the chromatic number
Improved bounds for the chromatic number of a graph
✍ S. Louis Hakimi; Edward Schmeichel 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 2 views

## Abstract After giving a new proof of a well‐known theorem of Dirac on critical graphs, we discuss the elegant upper bounds of Matula and Szekeres‐Wilf which follow from it. In order to improve these bounds, we consider the following fundamental coloring problem: given an edge‐cut (__V__~1~, __V_

An upper bound on the sum of squares of
An upper bound on the sum of squares of degrees in a graph
✍ D. de Caen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 163 KB

Let G be a simple graph with n vertices, e edges and vertex degrees &, d2 ..... d~. It is proved that d2+ ... +d~<~e(2e/(n-1)+ n-2) when n~>2. This bound does not generalize to all sequences of positive integers. A comparison is made to another upper bound on d 2 +. • -+ d 2, due to Sz6kely et al. (