×

Sharp bounds for decomposing graphs into edges and triangles. (English) Zbl 1466.05176

Summary: For a real constant \(\alpha\), let \(\pi_3^\alpha (G)\) be the minimum of twice the number of \(K_2\)’s plus \(\alpha\) times the number of \(K_3\)’s over all edge decompositions of \(G\) into copies of \(K_2\) and \(K_3\), where \(K_r\) denotes the complete graph on \(r\) vertices. Let \(\pi_3^\alpha (n)\) be the maximum of \(\pi_3^\alpha (G)\) over all graphs \(G\) with \(n\) vertices.
The extremal function \(\pi_3^3(n)\) was first studied by E. Györi and Z. Tuza [Stud. Sci. Math. Hung. 22, No. 1–4, 315–320 (1987; Zbl 0725.05068)]. In recent progress on this problem, D. Kral et al. [Comb. Probab. Comput. 28, No. 3, 465–472 (2019; Zbl 1436.05086)] proved via flag algebras that \(\pi_3^3(n)\leq (1/2+o(1)){n^2}\). We extend their result by determining the exact value of \(\pi_3^\alpha (n)\) and the set of extremal graphs for all \(\alpha\) and sufficiently large \(n\). In particular, we show for \(\alpha=3\) that \(K_n\) and the complete bipartite graph \(K_{\lfloor n/2 \rfloor,\lceil n/2 \rceil}\) are the only possible extremal examples for large \(n\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N.,Fischer, E.,Krivelevich, M. andSzegedy, M. (2000) Efficient testing of large graphs. Combinatorica20 451-476. · Zbl 1052.68096
[2] Barber, B.,Kühn, D.,Lo, A. andOsthus, D. (2016) Edge-decompositions of graphs with high minimum degree. Adv. Math.288 337-385. · Zbl 1328.05145
[3] Bollobás, B. (1998) Modern Graph Theory. Springer. · Zbl 0902.05016
[4] Chung, F. R. K. (1981) On the decomposition of graphs. SIAM J. Algebraic Discrete Methods2 1-12. · Zbl 0499.05046
[5] Delcourt, M. andPostle, L. (2019) Progress towards Nash-Williams’ conjecture on triangle decompositions. arXiv:1909.00514
[6] Dross, F. (2016) Fractional triangle decompositions in graphs with large minimum degree. SIAM J. Discrete Math.30 36-42. · Zbl 1329.05244
[7] Dukes, P. andHorsley, D. (2020) On the minimum degree required for a triangle decomposition. SIAM J. Discrete Math.34 597-610. · Zbl 1431.05120
[8] Erdős, P. (1967) Some recent results on extremal problems in graph theory: results. In Theory of Graphs (Internat. Sympos., Rome, 1966), pp. 117-123 (English), pp. 124-130 (French). Gordon & Breach. · Zbl 0187.21003
[9] Erdős, P. (1971) Some unsolved problems in graph theory and combinatorial analysis. In Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), pp. 97-109. Academic Press. · Zbl 0221.05051
[10] Erdős, P.,Goodman, A.W. And Pósa, L. (1966) The representation of a graph by set intersections. Canad. J. Math.18 106-112. · Zbl 0137.43202
[11] Győri, E. (1988) On the number of edge-disjoint triangles in graphs of given size. In Combinatorics (Eger, 1987), Vol. 52 of Colloquia Mathematica Societatis János Bolyai, pp. 267-276. North-Holland. · Zbl 0706.05029
[12] Győri, E. (1991) On the number of edge disjoint cliques in graphs of given size. Combinatorica11 231-243. · Zbl 0755.05049
[13] Győri, E. (1992) Edge disjoint cliques in graphs. In Sets, Graphs and Numbers (Budapest, 1991), Vol. 60 of Colloquia Mathematica Societatis János Bolyai, pp. 357-363. North-Holland. · Zbl 0785.05054
[14] Győri, E. andKeszegh, B. (2017) On the number of edge-disjoint triangles in K_4-free graphs. Combinatorica37 1113-1124. · Zbl 1399.05123
[15] Győri, E. andKostochka, A. V. (1979) On a problem of G. O. H. Katona and T. Tarján. Acta Math. Acad. Sci. Hungar.34 321-327. · Zbl 0463.05054
[16] Győri, E. andTuza, Z. (1987) Decompositions of graphs into complete subgraphs of given order. Studia Sci. Math. Hungar.22 315-320. · Zbl 0725.05068
[17] Haxell, P.E. And Rödl, V. (2001) Integer and fractional packings in dense graphs. Combinatorica21 13-38. · Zbl 1107.05304
[18] Kahn, J. (1981) Proof of a conjecture of Katona and Tarján. Period. Math. Hungar.12 81-82. · Zbl 0429.05049
[19] Král’, D.,Lidický, B.,Martins, T.L. And Pehova, Y. (2019) Decomposing graphs into edges and triangles. Combin. Probab. Comput.28 465-472. · Zbl 1436.05086
[20] Liu, H.,Pikhurko, O. andStaden, K. (2020) The exact minimum number of triangles in graphs of given order and size. Forum Math. Pi8 e8. · Zbl 1439.05108
[21] Nash-Williams, C. (1970) An unsolved problem concerning decomposition of graphs into triangles. In Combinatorial Theory and Its Applications III, pp. 1179-1183. North-Holland.
[22] Pikhurko, O. andRazborov, A. (2017) Asymptotic structure of graphs with the minimum number of triangles. Combin. Probab. Comput.26 138-160. · Zbl 1371.05147
[23] Pyber, L. (1992) Covering the edges of a graph by …. In Sets, Graphs and Numbers (Budapest, 1991), Vol. 60 of Colloquia Mathematica Societatis János Bolyai, pp. 583-610. North-Holland. · Zbl 0792.05110
[24] Razborov, A. (2007) Flag algebras. J. Symb. Logic72 1239-1282. · Zbl 1146.03013
[25] Razborov, A. (2008) On the minimal density of triangles in graphs. Combin. Probab. Comput.17 603-618. · Zbl 1170.05036
[26] Simonovits, M. (1968) A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pp. 279-319. Academic Press. · Zbl 0164.24604
[27] Tuza, Z. (2001) Unsolved combinatorial problems, Part I. BRICS Lecture Series LS-01-1.
[28] Yuster, R. (2005) Integer and fractional packing of families of graphs. Random Struct. Algorithms26 110-118. · Zbl 1061.05076
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.