arXiv Analytics

Sign in

arXiv:math/0209087 [math.CO]AbstractReferencesReviewsResources

On the non-3-colourability of random graphs

O. Dubois, J. Mandler

Published 2002-09-09Version 1

We show that for c >= 2.4682, a random graph on n vertices with c n (1+o(1)) edges almost surely has no 3-colouring. This improves on the current best upper bound of 2.4947.

Comments: 9 pages, 1 figure
Categories: math.CO
Subjects: 05C80, 05C15
Related articles: Most relevant | Search more
arXiv:1402.6466 [math.CO] (Published 2014-02-26)
Bipartite decomposition of random graphs
arXiv:0907.4211 [math.CO] (Published 2009-07-24)
The scaling window for a random graph with a given degree sequence
arXiv:1005.5716 [math.CO] (Published 2010-05-31, updated 2011-07-07)
Pancyclic subgraphs of random graphs

Links

Toolbox