TY - GEN A1 - Coja-Oghlan, Amin A1 - Taraz, Anusch T1 - Colouring random graphs in expected polynomial time N2 - We investigate the problem of colouring random graphs G ? G(n, p) in polynomial expected time. For the case p < 1.01/n, we present an algorithm that finds an optimal colouring in linear expected time. For suficiently large values of p, we give algorithms which approximate the chromatic number within a factor of O(?np). As a byproduct, we obtain an O(?np/ ln(np))-approximation algorithm for the independence number which runs in polynomial expected time provided p ? ln6 n/n. Y1 - 2004 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/125 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-1258 ER -