Decomposition of bounded degree graphs into C-4-free subgraphs

作者：Kang Ross J^*; Perarnau Guillem

来源：European Journal of Combinatorics, 2015, 44: 99-105.

DOI：10.1016/j.ejc.2014.09.009

We prove that every graph with maximum degree Delta admits a partition of its edges into O(root Delta) parts (as Delta -> infinity) 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.

• 出版日期2015-2
• 单位McGill