%0 Journal Article %F METIVIER-2010-675423 %A Métivier, Yves %A Robson, John Michael %A Saheb-Djahromi, Nasser %A Zemmari, Akka %T About Randomised Distributed Graph Colouring and Graph Partition Algorithms %J Information and Computation %V 208 %N 11 %P 1296-1304 %X We present and analyse a very simple randomised distributed vertex colouring algorithm for arbitrary graphs of size $n$ that halts in time $O(\log n)$ with probability $1-o(n^{-1}).$ Each message containing $1$ bit, its bit complexity per channel is $O(\log n)$. From this algorithm, we deduce and analyse a randomised distributed vertex colouring algorithm for arbitrary graphs of maximum degree $\Delta$ and size $n$ that uses at most $\Delta+1$ colours and halts in time $O(\log n)$ with probability $1-o(n^{-1}).$ We also obtain a partition algorithm for arbitrary graphs of size $n$ that builds a spanning forest in time $O(\log n)$ with probability $1-o(n^{-1})$. We study some parameters such as the number, the size and the radius of trees of the spanning forest %U http://hal.archives-ouvertes.fr/hal-00675423 %8 September %D 2010