Decomposition of bounded degree graphs into C₄-free subgraphs

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

Authors Ross J. Kang, Guillem Perarnau

Publication date 19 November 2014

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3520447 (Why is no real title available?)
• A note on the Turán function of even cycles
• Decomposition of Finite Graphs Into Forests
• Degree Ramsey numbers for cycles and blowups of trees
• Degree Ramsey numbers of graphs
• Existence of spanning \(\mathcal{F}\)-free subgraphs with large minimum degree
• Generalised Ramsey numbers for small graphs
• Graph colouring and the probabilistic method
• Multi-color Ramsey numbers of even cycles
• On multicolor Ramsey numbers for complete bipartite graphs
• Sparsity. Graphs, structures, and algorithms
• The history of degenerate (bipartite) extremal graph problems

Cited in

(6)

• Degree bipartite Ramsey numbers
• Degree Ramsey numbers for even cycles
• Multicolor list Ramsey numbers grow exponentially
• Decomposing \(C_4\)-free graphs under degree constraints
• Large P₄‐free graphs with bounded degree
• Every graph of sufficiently large average degree contains a \(C_4\)-free subgraph of large average 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)