Decomposition of bounded degree graphs into C4-free subgraphs

Ross Kang; Guillem Perarnau

doi:10.1016/j.ejc.2014.09.009

Decomposition of bounded degree graphs into C₄-free subgraphs

Ross Kang, Guillem Perarnau

Mathematics

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

82 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 C₄ as a subgraph. This bound is sharp up to a constant factor. Our proof uses an iterated random colouring procedure.

Original language	English
Pages (from-to)	99-105
Number of pages	7
Journal	European Journal of Combinatorics
Volume	44
Issue number	A
Early online date	15 Oct 2014
DOIs	https://doi.org/10.1016/j.ejc.2014.09.009
Publication status	Published - Feb 2015

Access to Document

10.1016/j.ejc.2014.09.009Licence: Other (please provide link to licence statement

KangRJ2015DecompositionFinal published version, 368 KBLicence: Other (please provide link to licence statement

https://doi.org/10.1016/j.ejc.2014.09.009Licence: Other (please provide link to licence statement

Cite this

@article{52df106a06a94ca0a763ed1bc9424e33,

title = "Decomposition of bounded degree graphs into C4-free subgraphs",

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.",

author = "Ross Kang and Guillem Perarnau",

year = "2015",

month = feb,

doi = "10.1016/j.ejc.2014.09.009",

language = "English",

volume = "44",

pages = "99--105",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Elsevier",

number = "A",

}

TY - JOUR

T1 - Decomposition of bounded degree graphs into C4-free subgraphs

AU - Kang, Ross

AU - Perarnau, Guillem

PY - 2015/2

Y1 - 2015/2

N2 - 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.

AB - 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.

U2 - 10.1016/j.ejc.2014.09.009

DO - 10.1016/j.ejc.2014.09.009

M3 - Article

SN - 0195-6698

VL - 44

SP - 99

EP - 105

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - A

ER -

Decomposition of bounded degree graphs into C4-free subgraphs

Abstract

Access to Document

Fingerprint

Cite this

Decomposition of bounded degree graphs into C₄-free subgraphs