On the non-3-colourability of random graphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
9 pages, 1 figure

Keywords

Combinatorics, 05C80; 05C15

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/64883

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0209087
 http://arxiv.org/abs/math/0209087

Collections

arXiv