Decomposition of bounded degree graphs into C4-free subgraphs

Ross Kang, Guillem Perarnau

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
83 Downloads (Pure)


We prove that every graph with maximum degree ∆ admits a partition of its edges into O(√∆) parts (as ∆→∞) none of which contains C4 as a subgraph. This bound is sharp up to a constant factor. Our proof uses an iterated random colouring procedure.
Original languageEnglish
Pages (from-to)99-105
Number of pages7
JournalEuropean Journal of Combinatorics
Issue numberA
Early online date15 Oct 2014
Publication statusPublished - Feb 2015


Dive into the research topics of 'Decomposition of bounded degree graphs into C4-free subgraphs'. Together they form a unique fingerprint.

Cite this