A natural method to avoid memory access conflicts in EREW-PRAM graph algorithms is to compute a large independent set in a constant-degree-bounded conflict graph. Many EREW-PRAM algorithms use results from \cite{CoVi86}, \cite{GoPlSh87}, which can be used to compute such a set in $\O$$(\log^* n)$ parallel time. This paper gives an $\O$$(1)$ time randomized algorithm using $\O$$(n)$ processors for that problem. Our algorithm improves with high probability the running time of many EREW-PRAM algorithms.