No label defined (Q3975003)

[For the entire collection see Zbl 0726.00010.] This paper describes a parallel implementation of the greedy colouring algorithm which colours almost all graphs with \(n\) vertices by at most \[ \left(1+{1\over \log_ 2\log_ 2\log_ 2 n}\right){n\over \log_ 2 n} \] colours (the probability that a random graph with \(n\) vertices is coloured by more colours is \(o(n^{-k})\) for each fixed \(k\)). The model of parallel machine is PRIORITY concurrent read concurrent write PRAM. The algorithm has a worst case parallel running time of \(O(\log^ 2_ 2 n \log_ 2\log_ 2 n)\) and uses \(O(n^ 2\log_ 2^{-2}n)\) processors. The number of colours used by the parallel algorithm is roughly the same as the number of colours uses by the sequential greedy algorithm and approximately twice the expected value of the chromatic number of the graph.