Decomposition of bounded degree graphs into $C_4$-free subgraphs

Abstract

We prove that every graph with maximum degree $\Delta$ admits a partition of its edges into $O(\sqrt{\Delta })$ parts (as $\Delta \to \infty$) none of which contains $C_4$ as a subgraph. This bound is sharp up to a constant factor. Our proof uses an iterated random colouring procedure.

8 pages; to appear in European Journal of Combinatorics

References in corpus (1)

• Existence of spanning $\mathcal{F}$-free subgraphs with large minimum degree

Cited by in corpus (1)

• Degree bipartite Ramsey numbers