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)

Abstract

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
Volume44
Issue numberA
Early online date15 Oct 2014
DOIs
Publication statusPublished - Feb 2015

Fingerprint

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

Cite this