Purification of large bicolorable graph states

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.