Tree densities in sparse graph classes. (English) Zbl 1506.90260
Summary: What is the maximum number of copies of a fixed forest \(T\) in an \(n\)-vertex graph in a graph class \(\mathcal{G}\) as \(n\to\infty\) ? We answer this question for a variety of sparse graph classes \(\mathcal{G}\) . In particular, we show that the answer is \(\Theta(n^{\alpha_d(T)})\) where \(\alpha_d(T)\) is the size of the largest stable set in the subforest of \(T\) induced by the vertices of degree at most \(d\), for some integer \(d\) that depends on \(\mathcal{G}\) . For example, when \(\mathcal{G}\) is the class of \(k\)-degenerate graphs then \(d=k\) ; when \(\mathcal{G}\) is the class of graphs containing no \(K_{s,t}\) -minor \((t\geqslant s\) ) then \(d=s-1\) ; and when \(\mathcal{G}\) is the class of \(k\)-planar graphs then \(d=2\) . All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs.
References:
| [1] | Alameddine, A. F., On the number of cycles of length \(4\) in a maximal planar graph. J. Graph Theory4(1980), no. 4, 417-422. · Zbl 0419.05035 |
| [2] | Alexander, J., Cutler, J., and Mink, T., Independent sets in graphs with given minimum degree. Electron. J. Combin.19(2012), no. 3, P37. · Zbl 1252.05157 |
| [3] | Alon, N. and Caro, Y., On the number of subgraphs of prescribed type of planar graphs with a given number of vertices. In: Convexity and graph theory, North-Holland Math. Stud., 86, North-Holland, 1984, pp. 25-36. · Zbl 0566.05024 |
| [4] | Alon, N., Kostochka, A., and Shikhelman, C., Many cliques in \(H\) -free subgraphs of random graphs. J. Comb.9(2018), no. 4, 567-597. · Zbl 1401.05266 |
| [5] | Alon, N. and Shikhelman, C., Many \(T\) copies in \(H\) -free graphs. J. Combin. Theory Ser. B121(2016), 146-172. · Zbl 1348.05100 |
| [6] | Alon, N. and Shikhelman, C., \(H\) -free subgraphs of dense graphs maximizing the number of cliques and their blow-ups. Discrete Math.342(2019), no. 4, 988-996. · Zbl 1405.05050 |
| [7] | Alweiss, R., Lovett, S., Wu, K., and Zhang, J., Improved bounds for the sunflower lemma. In: Proc. 52nd Annual ACM Symp. on Theory of Computing (STOC 2020), 2020, pp. 624-630. · Zbl 07298275 |
| [8] | Bae, S. W., Baffier, J.-F., Chun, J., Eades, P., Eickmeyer, K., Grilli, L., Hong, S.-H., Korman, M., Montecchiani, F., Rutter, I., and Tóth, C. D., Gap-planar graphs. Theor. Comput. Sci.745(2018), 36-52. · Zbl 1400.68151 |
| [9] | Bell, T., Chueluecha, S., and Warnke, L., Note on sunflowers. Discrete Math.344(2021), no. 7, 112367. · Zbl 1466.05204 |
| [10] | Biedl, T. and Wilkinson, D. F., Bounded-degree independent sets in planar graphs. Theory Comput. Syst.38(2005), no. 3, 253-278. · Zbl 1101.68717 |
| [11] | Bienstock, D., Robertson, N., Seymour, P. D., and Thomas, R., Quickly excluding a forest. J. Combin. Theory Ser. B52(1991), no. 2, 274-283. · Zbl 0763.05023 |
| [12] | Bose, P., Dujmović, V., and Wood, D. R., Induced subgraphs of bounded treewidth and bounded degree. Contrib. Discrete Math.1(2006), no. 1, 88-105. · Zbl 1092.05033 |
| [13] | Bose, P., Smid, M., and Wood, D. R., Light edges in degree-constrained graphs. Discrete Math.282(2004), nos. 1-3, 35-41. MR:2059504. · Zbl 1042.05078 |
| [14] | Chase, Z., The maximum number of triangles in a graph of given maximum degree. Adv. Combin. (2020), 5-10. · Zbl 1450.05040 |
| [15] | Chen, Z.-Z., Approximation algorithms for independent sets in map graphs. J. Algorithms41(2001), no. 1, 20-40. · Zbl 1002.68111 |
| [16] | Chen, Z.-Z., New bounds on the edge number of a \(k\) -map graph. J. Graph Theory55(2007), no. 4, 267-290. · Zbl 1124.05029 |
| [17] | Chen, Z.-Z., Grigni, M., and Papadimitriou, C. H., Map graphs. J. ACM. 49(2002), no. 2, 127-138. · Zbl 1323.05039 |
| [18] | Conway, J. H. and Gordon, C. M., Knots and links in spatial graphs. J. Graph Theory7(1983), 445-453. · Zbl 0524.05028 |
| [19] | Cutler, J. and Radcliffe, A. J., Extremal problems for independent set enumeration. Electron. J. Combin.18(2011), no. 1, P169. · Zbl 1229.05138 |
| [20] | Cutler, J. and Radcliffe, A. J., The maximum number of complete subgraphs in a graph with given maximum degree. J. Combin. Theory Ser. B104(2014), 60-71. · Zbl 1282.05073 |
| [21] | Cutler, J. and Radcliffe, A. J., The maximum number of complete subgraphs of fixed size in a graph with given maximum degree. J. Graph Theory84(2017), no. 2, 134-145. · Zbl 1354.05104 |
| [22] | De Mendez, P. O., Oum, S.-I., and Wood, D. R., Defective colouring of graphs excluding a subgraph or minor. Combinatorica39(2019), no. 2, 377-410. · Zbl 1438.05102 |
| [23] | De Verdière, Y. C., Sur un nouvel invariant des graphes et un critère de planarité. J. Combin. Theory Ser. B50(1990), no. 1, 11-21. · Zbl 0742.05061 |
| [24] | De Verdière, Y. C., On a new graph invariant and a criterion for planarity. In: Graph structure theory, Contemp. Math., 147, Amer. Math. Soc., 1993, pp. 137-147. · Zbl 0791.05024 |
| [25] | Demaine, E. D., Fomin, F. V., Hajiaghayi, M., and Thilikos, D. M., Fixed-parameter algorithms for \(\left(k,r\right)\) -center in planar graphs and map graphs. ACM Trans. Algorithms1(2005), no. 1, 33-47. · Zbl 1321.05256 |
| [26] | Dujmović, V., Eppstein, D., and Wood, D. R., Structure of graphs with locally restricted crossings. SIAM J. Discrete Math.31(2017), no. 2, 805-824. · Zbl 1362.05121 |
| [27] | Dujmović, V., Fijavž, G., Joret, G., Sulanke, T., and Wood, D. R., On the maximum number of cliques in a graph embedded in a surface. European J. Combin.32(2011), no. 8, 1244-1252. · Zbl 1229.05139 |
| [28] | Dujmović, V., Morin, P., and Wood, D. R., Graph product structure for non-minor-closed classes. 2019. arXiv:1907.05168 |
| [29] | Eckhoff, J., The maximum number of triangles in a \({K}_4\) -free graph. Discrete Math.194(1999), nos. 1-3, 95-106. · Zbl 0933.05078 |
| [30] | Eckhoff, J., A new Turán-type theorem for cliques in graphs. Discrete Math.282(2004), nos. 1-3, 113-122. · Zbl 1042.05053 |
| [31] | Engbers, J. and Galvin, D., Counting independent sets of a fixed size in graphs with a given minimum degree. J. Graph Theory76(2014), no. 2, 149-168. · Zbl 1294.05121 |
| [32] | Eppstein, D., Connectivity, graph minors, and subgraph multiplicity. J. Graph Theory17(1993), no. 3, 409-416. · Zbl 0781.05029 |
| [33] | Eppstein, D. and Gupta, S., Crossing patterns in nonplanar road networks. In: Proc. 25th ACM SIGSPATIAL Int’l Conf. on Advances in Geographic Information Systems, 40, 2017, pp. 1-9. |
| [34] | Erdős, P. and Rado, R., Intersection theorems for systems of sets. J. London Math. Soc. Second Ser.35(1960), no. 1, 85-90. · Zbl 0103.27901 |
| [35] | Erdős, P. and Stone, A. H., On the structure of linear graphs. Bull. Amer. Math. Soc.52(1946), 1087-1091. · Zbl 0063.01277 |
| [36] | Ergemlidze, B., Methuku, A., Salia, N., and Győri, E., A note on the maximum number of triangles in a \({C}_5\) -free graph. J. Graph Theory90(2019), no. 3, 227-230. · Zbl 1407.05133 |
| [37] | Fiorini, S., Joret, G., Theis, D. O., and Wood, D. R., Small minors in dense graphs. Eur. J. Combin.33(2012), no. 6, 1226-1245. · Zbl 1242.05260 |
| [38] | Fisher, D. C. and Ryan, J., Conjectures on the number of complete subgraphs. In: Proc. 20th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, 70, pp. 217-219. 1990. · Zbl 0701.05026 |
| [39] | Fisher, D. C. and Ryan, J., Bounds on the number of complete subgraphs. Discrete Math.103(1992), no. 3, 313-320. · Zbl 0817.05035 |
| [40] | Foisy, J., Intrinsically knotted graphs. J. Graph Theory39(2002), no. 3, 178-187. · Zbl 1176.05022 |
| [41] | Fomin, F. V., Lokshtanov, D., and Saurabh, S., Bidimensionality and geometric graphs. In: Proc. 23rd Annual ACM-SIAM Symp. on Discrete Algorithms, 2012, pp. 1563-1575. · Zbl 1421.68126 |
| [42] | Fomin, F. V., Oum, S.-I., and Thilikos, D. M., Rank-width and tree-width of \(H\) -minor-free graphs. Eur. J. Combin.31(2010), no. 7, 1617-1628. · Zbl 1215.05171 |
| [43] | Fox, J. and Wei, F., On the number of cliques in graphs with a forbidden minor. J. Combin. Theory Ser. B126(2017), 175-197. · Zbl 1368.05110 |
| [44] | Fox, J. and Wei, F., On the number of cliques in graphs with a forbidden subdivision or immersion. SIAM J. Discrete Math.34(2020), no. 4, 2556-2582. · Zbl 1459.05132 |
| [45] | Frohmader, A., A Kruskal-Katona type theorem for graphs. J. Combin. Theory Ser. A117(2010), no. 1, 17-37. · Zbl 1230.05174 |
| [46] | Galvin, D., Two problems on independent sets in graphs. Discrete Math.311(2011), no. 20, 2105-2112. · Zbl 1228.05228 |
| [47] | Gan, W., Loh, P.-S., and Sudakov, B., Maximizing the number of independent sets of a fixed size. Combin. Probab. Comput.24(2015), no. 3, 521-527. · Zbl 1371.05213 |
| [48] | Gerbner, D., Győri, E., Methuku, A., and Vizer, M., Generalized Turán problems for even cycles. J. Combin. Theory Ser. B145(2020), 169-213. · Zbl 1448.05107 |
| [49] | Gerbner, D., Methuku, A., and Vizer, M., Generalized Turán problems for disjoint copies of graphs. Discrete Math.342(2019), no. 11, 3130-3141. · Zbl 1419.05110 |
| [50] | Gerbner, D. and Palmer, C., Counting copies of a fixed subgraph in \(F\) -free graphs. Eur. J. Combin.82(2019), 103001. · Zbl 1419.05104 |
| [51] | Goldberg, F. and Berman, A., On the Colin de Verdière number of graphs. Linear Algebra Appl.434(2011), no. 7, 1656-1662. · Zbl 1221.05259 |
| [52] | Goldberg, N., Mattman, T. W., and Naimi, R., Many, many more intrinsically knotted graphs. Algebr. Geom. Topol.14(2014), no. 3, 1801-1823. · Zbl 1292.05091 |
| [53] | Győri, E., Paulos, A., Salia, N., Tompkins, C., and Zamora, O., The maximum number of paths of length three in a planar graph. Preprint 2019. arXiv:1909.13539 |
| [54] | Győri, E., Paulos, A., Salia, N., Tompkins, C., and Zamora, O., The maximum number of pentagons in a planar graph. Preprint 2019. arXiv:1909.13532 |
| [55] | Győri, E., Salia, N., Tompkins, C., and Zamora, O., The maximum number of \({P}_{\ell }\) copies in \({P}_k\) -free graphs. Discrete Math. Theor. Comput. Sci.21(2019), 14. · Zbl 1417.05106 |
| [56] | Harant, J., Horňák, M., and Skupień, Z., Separating 3-cycles in plane triangulations. Discrete Math.239(2001), nos. 1-3, 127-136. · Zbl 0983.05057 |
| [57] | Harvey, D. J. and Wood, D. R., Parameters tied to treewidth. J. Graph Theory84(2017), no. 4, 364-385. · Zbl 1359.05030 |
| [58] | Hedman, B., The maximum number of cliques in dense graphs. Discrete Math.54(1985), no. 2, 161-166. · Zbl 0569.05029 |
| [59] | Huynh, T., Joret, G., and Wood, R. D., Subgraph densities in a surface, Preprint, 2020, arXiv:2003.13777 |
| [60] | Kahn, J., An entropy approach to the hard-core model on bipartite graphs. Combin. Probab. Comput.10(2001), no. 3, 219-237. · Zbl 0985.60088 |
| [61] | Khadzhiivanov, N. and Nenov, N., Sharp estimates of the highest number of cliques of a graph. Annuaire Univ. Sofia Fac. Math. Méc.70(1975/76), 23-26. · Zbl 0493.05055 |
| [62] | Kirsch, R. and Radcliffe, A. J., Many triangles with few edges. Electron. J. Combin.26(2019), no. 2, P2.36. · Zbl 1414.05161 |
| [63] | Kobourov, S. G., Liotta, G., and Montecchiani, F., An annotated bibliography on 1-planarity. Comput. Sci. Rev.25(2017), 49-67. · Zbl 1398.68402 |
| [64] | König, D., Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe, Akademische Verlagsgesellschaft, Leipzig, 1936. · Zbl 0013.22803 |
| [65] | Kostochka, A. V., Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica4(1984), no. 4, 307-316. · Zbl 0555.05030 |
| [66] | Lee, C. and Oum, S.-I., Number of cliques in graphs with a forbidden subdivision. SIAM J. Disc. Math.29(2015), no. 4, 1999-2005. · Zbl 1323.05074 |
| [67] | Letzter, S., Many \(H\) -copies in graphs with a forbidden tree. SIAM J. Discrete Math33(2019), no. 4, 2360-2368. · Zbl 1428.05056 |
| [68] | Louis Hakimi, S., On the degrees of the vertices of a directed graph. J. Franklin Inst.279(1965), 290-308. · Zbl 0173.26404 |
| [69] | Hakimi, S. Louis and Schmeichel, E. F., On the number of cycles of length \(k\) in a maximal planar graph. J. Graph Theory3(1979), no. 1, 69-86. · Zbl 0395.05046 |
| [70] | Hakimi, S. Louis and Schmeichel, E. F., Bounds on the number of cycles of length three in a planar graph. Israel J. Math.41(1982), nos. 1-2, 161-180. · Zbl 0484.05033 |
| [71] | Luo, R., The maximum number of cliques in graphs without long cycles. J. Combin. Theory Ser. B128(2018), 219-226. · Zbl 1375.05147 |
| [72] | Ma, J. and Qiu, Y., Some sharp results on the generalized Turán numbers. Eur. J. Combin.84(2020), 103026. · Zbl 1428.05141 |
| [73] | Mader, W., Homomorphiesätze für Graphen. Math. Ann.178(1968), 154-168. · Zbl 0165.57401 |
| [74] | Mohar, B. and Thomassen, C., Graphs on surfaces. Johns Hopkins University Press, 2001. · Zbl 0979.05002 |
| [75] | Montgomery, R., Logarithmically small minors and topological minors. J. London Math. Soc.91(2015), no. 1, 71-88. · Zbl 1307.05209 |
| [76] | Nešetřil, J. and De Mendez, P. O., How many \(F\) ’s are there in \(G\) ?Eur. J. Combin.32(2011), no. 7, 1126-1141. · Zbl 1229.05212 |
| [77] | Nešetřil, J. and De Mendez, P. O., Sparsity. Algorithms and Combinatorics, 28, Springer, 2012. · Zbl 1268.05002 |
| [78] | Nešetřil, J. and De Mendez, P. O., On low tree-depth decompositions. Graphs Combin31(2015), no. 6, 1941-1963. · Zbl 1327.05279 |
| [79] | Norine, S., Seymour, P., Thomas, R., and Wollan, P., Proper minor-closed families are small. J. Combin. Theory Ser. B96(2006), no. 5, 754-757. · Zbl 1093.05065 |
| [80] | Pach, J. and Tóth, G., Recognizing string graphs is decidable. Discrete Comput. Geom.28(2002), no. 4, 593-606. · Zbl 1050.68111 |
| [81] | Papadimitriou, C. H. and Yannakakis, M., The clique problem for planar graphs. Inform. Process. Lett.13(1981), nos. 4-5, 131-133. |
| [82] | Petingi, L. and Rodriguez, J., A new proof of the Fisher-Ryan bounds for the number of cliques of a graph. In: Proc. 31st Southeastern Int’l Conf. on Combinatorics, Graph Theory and Computing, Congr. Numer., 146, 2000, pp. 143-146. · Zbl 0976.05034 |
| [83] | Ramírez Alfonsín, J. L., Knots and links in spatial graphs: a survey. Discrete Math302(2005), nos. 1-3, 225-242. · Zbl 1078.57004 |
| [84] | Reed, B. and Wood, D. R., A linear time algorithm to find a separator in a graph excluding a minor. ACM Trans. Algorithms5(2009), no. 4, 39. · Zbl 1298.05308 |
| [85] | Reed, B. A., Tree width and tangles: a new connectivity measure and some applications. In: Bailey, R. A. (ed.), Surveys in combinatorics, London Math. Soc. Lecture Note Ser., 241, Cambridge Univ. Press, 1997, pp. 87-162. · Zbl 0895.05034 |
| [86] | Ringel, G., Das Geschlecht des vollständigen paaren Graphen. Abh. Math. Sem. Univ. Hamburg28(1965), 139-150. · Zbl 0132.21203 |
| [87] | Robertson, N., Seymour, P., and Thomas, R., A survey of linkless embeddings. In: Robertson, N. and Seymour, P. (eds.), Graph structure theory, Proc. AMS-IMS-SIAM Joint Summer Research Conf. on Graph Minors, Contemporary Math., 147, Amer. Math. Soc., 1993, pp. 125-136. · Zbl 0788.05034 |
| [88] | Robertson, N., Seymour, P., and Thomas, R., Sachs’ linkless embedding conjecture. J. Combin. Theory Ser. B64(1995), 185-227. · Zbl 0832.05032 |
| [89] | Sachs, H., On a spatial analogue of Kuratowski’s theorem on planar graphs — an open problem. In: Borowiecki, M., Kennedy, J. W., and Syslo, M. M. (eds.), Proc. Conf. on Graph Theory, Lecture Notes in Math., 1018, Springer, 1983, pp. 230-241. · Zbl 0525.05024 |
| [90] | Schrijver, A., Minor-monotone graph invariants. In: Surveys in combinatorics, London Math. Soc. Lecture Note Ser., 241, Cambridge Univ. Press, 1997, pp. 163-196. · Zbl 0883.05044 |
| [91] | Shapira, A. and Sudakov, B., Small complete minors above the extremal edge density. Combinatorica35(2015), no. 1, 75-94. · Zbl 1363.05241 |
| [92] | Shimabara, M., Knots in certain spatial graphs. Tokyo J. Math11(1988), no. 2, 405-413. · Zbl 0669.57001 |
| [93] | Thomason, A., An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc95(1984), no. 2, 261-265. · Zbl 0551.05047 |
| [94] | Turán, P., On an extremal problem in graph theory. Mat. Fiz. Lapok48(1941), 436-452. · Zbl 0026.26903 |
| [95] | Van Batenburg, W. C., Huynh, T., Joret, G., and Raymond, J.-F., A tight Erdős-Pósa function for planar minors. Adv. Combin.2(2019). · Zbl 1450.05085 |
| [96] | Van Der Holst, H., Lovász, L., and Schrijver, A., The Colin de Verdière graph parameter. In: Graph theory and combinatorial biology, Bolyai Soc. Math. Stud., 7, János Bolyai Math. Soc., 1999, pp. 29-85. · Zbl 0930.05065 |
| [97] | Wood, D. R., On the maximum number of cliques in a graph. Graphs Combin.23(2007), no. 3, 337-352. · Zbl 1122.05048 |
| [98] | Wormald, N. C., On the frequency of \(3\) -connected subgraphs of planar graphs. Bull. Austral. Math. Soc.34(1986), no. 2, 309-317. · Zbl 0584.05030 |
| [99] | Zykov, A. A., On some properties of linear complexes. Mat. Sbornik N.S.24(1949), no. 66, 163-188. · Zbl 0033.02602 |
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.
