  We describe novel purification protocols for bicolorable graph states. The
protocols scale efficiently for large graph states. We introduce a method of
analysis that allows us to derive simple recursion relations characterizing
their behavior as well as analytical expressions for their thresholds and fixed
point behavior. We introduce two purification protocols with high threshold.
They can, for graph degree four, tolerate 1% (3%) gate error or 20% (30%) local
error.
