On the non-3-colourability of random graphs

arXivmath/0209087MaRDI QIDQ6472096FDOQ6472096

Authors: Olivier Dubois, Jacques Mandler 

Publication date: 9 September 2002

Abstract: 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.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: On the non-3-colourability of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6472096)