×

Decomposition of bounded degree graphs into \(C_4\)-free subgraphs. (English) Zbl 1302.05141

Summary: We prove that every graph with maximum degree \(\Delta\) admits a partition of its edges into \(O(\sqrt{\Delta})\) parts (as \(\Delta \to \infty\)) 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.

MSC:

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

References:

[1] Burr, S. A.; Erdős, P.; Lovász, L., On graphs of Ramsey type, Ars Combin., 1, 1, 167-190 (1976) · Zbl 0333.05120
[2] Chung, F. R.K.; Graham, R. L., On multicolor Ramsey numbers for complete bipartite graphs, J. Combin. Theory Ser. B, 18, 164-169 (1975) · Zbl 0298.05122
[3] Erdős, P., On sequences of integers no one of which divides the product of two others and on some related problems, Inst. Math. Mech. Univ. Tomsk, 2, 74-82 (1938) · JFM 64.0988.02
[4] Füredi, Z.; Simonovits, M., The history of degenerate (bipartite extremal graph problems), (Erdős Centennial. Erdős Centennial, Bolyai Soc. Math. Stud., vol. 25 (2013), János Bolyai Math. Soc.: János Bolyai Math. Soc. Budapest), 169-264 · Zbl 1296.05098
[5] Irving, R. W., Generalised Ramsey numbers for small graphs, Discrete Math., 9, 251-264 (1974) · Zbl 0287.05104
[6] Jiang, T.; Milans, K. G.; West, D. B., Degree Ramsey numbers for cycles and blowups of trees, European J. Combin., 34, 2, 414-423 (2013) · Zbl 1277.05116
[7] Kinnersley, W. B.; Milans, K. G.; West, D. B., Degree Ramsey numbers of graphs, Combin. Probab. Comput., 21, 1-2, 229-253 (2012) · Zbl 1241.05092
[8] Li, Y.; Lih, K. W., Multi-color Ramsey numbers of even cycles, European J. Combin., 30, 1, 114-118 (2009) · Zbl 1223.05186
[9] Molloy, M.; Reed, B., (Graph Colouring and the Probabilistic Method. Graph Colouring and the Probabilistic Method, Algorithms and Combinatorics, vol. 23 (2002), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0987.05002
[10] Nash-Williams, C. St. J.A., Decomposition of finite graphs into forests, J. Lond. Math. Soc., 39, 12 (1964) · Zbl 0119.38805
[11] Nešetřil, J.; Ossona de Mendez, P., (Sparsity: Graphs, Structures, and Algorithms. Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28 (2012), Springer: Springer Heidelberg) · Zbl 1268.05002
[13] Pikhurko, O., A note on the Turán function of even cycles, Proc. Amer. Math. Soc., 140, 11, 3687-3692 (2012) · Zbl 1270.05061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.