On the non-3-colourability of random graphs

Simple item page
dc.creatorDubois, O.
dc.creatorMandler, J.
dc.date2002-09-09
dc.date.accessioned2026-07-07T04:50:41Z
dc.date.available2026-07-07T04:50:41Z
dc.descriptionWe 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.
dc.description9 pages, 1 figure
dc.identifierhttps://arxiv.org/abs/math/0209087
dc.identifierhttp://arxiv.org/abs/math/0209087
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/64883
dc.subjectCombinatorics
dc.subject05C80; 05C15
dc.titleOn the non-3-colourability of random graphs
dc.typetext

Files

Collections

arXiv