𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An improved upper bound on the non-3-colourability threshold

✍ Scribed by Paul E. Dunne; Michele Zito

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
470 KB
Volume
65
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we derive an improved upper bound on the average vertex degree, 6. needed to ensure that: Vc > 0 and n sufficiently large, a random n-vertex graph with at least (6 + E)&! edges is almost certainly not 3-colourable. @

πŸ“œ SIMILAR VOLUMES

An improved upper bound on the crossing
An improved upper bound on the crossing number of the hypercube
✍ Luerbio Faria; Celina Miraglia Herrera de Figueiredo; Ondrej SΓ½kora; Imrich Vrt' πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 288 KB

## Abstract We draw the __n__‐dimensional hypercube in the plane with ${5\over 32}4^{n}-\lfloor{{{{n}^{2}+1}\over 2}}\rfloor {2}^{n-2}$ crossings, which improves the previous best estimation and coincides with the long conjectured upper bound of ErdΓΆs and Guy. Β© 2008 Wiley Periodicals, Inc. J Graph