𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time

✍ Scribed by Michael Krivelevich; Van H. Vu

Book ID
110325380
Publisher
Springer US
Year
2002
Tongue
English
Weight
99 KB
Volume
6
Category
Article
ISSN
1382-6905

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The independence number of an edge-chrom
The independence number of an edge-chromatic critical graph
✍ Douglas R. Woodall πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 77 KB πŸ‘ 1 views

A graph G with maximum degree and edge chromatic number (G)> is edge--critical if (G -e) = for every edge e of G. It is proved here that the vertex independence number of an edge--critical graph of order n is less than 3 5 n. For large , this improves on the best bound previously known, which was ro