Decomposition of bounded degree graphs into C4C4-free subgraphs

We prove that every graph with maximum degree ΔΔ admits a partition of its edges into O(Δ) parts (as Δ→∞Δ→∞) none of which contains C4C4 as a subgraph. This bound is sharp up to a constant factor. Our proof uses an iterated random colouring procedure.