An NC algorithm for Brooks' Theorem

Brooks' Theorem states that any graph G of maximum degree Δ⩾3 can be Δ node colored if and only if G does not contain K Δ+1 as a subgraph. We exhibit an NC algorithm to find a Δ coloring when Brooks' Theorem guarantees it exists.

Authors

• Howard J. Karloff

Keywords

No keywords are indexed for this paper.