AN IMPROVED UPPER BOUND ON THE NON-3-COLORABILITY THRESHOLD

Authors
DUNNE PE ZITO M
Citation
Pe. Dunne et M. Zito, AN IMPROVED UPPER BOUND ON THE NON-3-COLORABILITY THRESHOLD, Information processing letters, 65(1), 1998, pp. 17-23
Citations number
9
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
65
Issue
1
Year of publication
1998
Pages
17 - 23
Database
ISI
SICI code
0020-0190(1998)65:1<17:AIUBOT>2.0.ZU;2-M
Abstract
In this paper we derive an improved upper bound on the average vertex degree, delta, needed to ensure that: For All epsilon > 0 and n suffic iently large, a random n-vertex graph with at least (delta+epsilon)n/2 edges is almost certainly not 3-colourable. (C) 1998 Elsevier Science B.V.