Decomposition of bounded degree graphs into C₄-free subgraphs

DOI10.1016/J.EJC.2014.09.009zbMATH Open1302.05141arXiv1408.1983OpenAlexW2143482081MaRDI QIDQ472402FDOQ472402

Authors: Ross J. Kang, Guillem Perarnau 

Publication date: 19 November 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1408.1983

Recommendations

• Decomposing \(C_4\)-free graphs under degree constraints
• Partitions of multigraphs without \(C_4\)
• On the exact decomposition threshold for even cycles
• Decomposing graphs of high minimum degree into 4-cycles
• Monochromatic bounded degree subgraph partitions

zbMATH Keywords

iterated random colouring

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The History of Degenerate (Bipartite) Extremal Graph Problems
• Title not available (Why is that?)
• Decomposition of Finite Graphs Into Forests
• Degree Ramsey numbers for cycles and blowups of trees
• Graph colouring and the probabilistic method
• Sparsity. Graphs, structures, and algorithms
• A note on the Turán function of even cycles
• On multicolor Ramsey numbers for complete bipartite graphs
• Multi-color Ramsey numbers of even cycles
• Generalised Ramsey numbers for small graphs
• Degree Ramsey numbers of graphs
• Existence of Spanning ℱ-Free Subgraphs with Large Minimum Degree

Cited In (5)

• Every graph of sufficiently large average degree contains a \(C_4\)-free subgraph of large average degree
• Degree Ramsey numbers for even cycles
• Degree bipartite Ramsey numbers
• Multicolor list Ramsey numbers grow exponentially
• Large P₄‐free graphs with bounded degree

This page was built for publication: Decomposition of bounded degree graphs into \(C_4\)-free subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472402)