×

Branch-depth: generalizing tree-depth of graphs. (English) Zbl 1458.05042

Summary: We present a concept called the branch-depth of a connectivity function, that generalizes the tree-depth of graphs. Then we prove two theorems showing that this concept aligns closely with the notions of tree-depth and shrub-depth of graphs as follows. For a graph \(G=(V,E)\) and a subset \(A\) of \(E\) we let \(\lambda_G(A)\) be the number of vertices incident with an edge in \(A\) and an edge in \(E\setminus A\). For a subset \(X\) of \(V\), let \(\rho_G(X)\) be the rank of the adjacency matrix between \(X\) and \(V\setminus X\) over the binary field. We prove that a class of graphs has bounded tree-depth if and only if the corresponding class of functions \(\lambda_G\) has bounded branch-depth and similarly a class of graphs has bounded shrub-depth if and only if the corresponding class of functions \(\rho_G\) has bounded branch-depth, which we call the rank-depth of graphs.
Furthermore we investigate various potential generalizations of tree-depth to matroids and prove that matroids representable over a fixed finite field having no large circuits are well-quasi-ordered by restriction.

MSC:

05C05 Trees
05B35 Combinatorial aspects of matroids and geometric lattices
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N., Asymptotically optimal induced universal graphs, Geom. Funct. Anal., 27, 1, 1-32 (2017) · Zbl 1358.05143
[2] Bodlaender, H. L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 6, 1305-1317 (1996) · Zbl 0864.68074
[3] Chan, T. F.N.; Cooper, J. W.; Koutecký, M.; Král’, D.; Pekárková, K., Optimal matrix tree-depth and a row-invariant parameterized algorithm for integer programming, (Czumaj, A.; Dawar, A.; Merelli, E., Proc. 47th Int. Coll. on Automata, Languages and Programming, ICALP 2020. Proc. 47th Int. Coll. on Automata, Languages and Programming, ICALP 2020, Leibniz International Proceedings in Informatics, LIPIcs, vol. 168 (2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik: Schloss Dagstuhl-Leibniz-Zentrum für Informatik Dagstuhl, Germany), 1-26
[4] Courcelle, B., The monadic second-order logic of graphs I: Recognizable sets of finite graphs, Inf. Comput., 85, 1, 12-75 (1990) · Zbl 0722.03008
[5] Courcelle, B.; Makowsky, J. A.; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33, 2, 125-150 (2000) · Zbl 1009.68102
[6] Ding, G., Subgraphs and well-quasi-ordering, J. Graph Theory, 16, 5, 489-502 (1992) · Zbl 0762.05093
[7] Ding, G.; Dziobiak, S.; Wu, H., Large \(W_k\)- or \(K_{3 , t}\)-minors in 3-connected graphs, J. Graph Theory, 82, 2, 207-217 (2016) · Zbl 1339.05376
[8] Ding, G.; Oporowski, B., On tree-partitions of graphs, Discrete Math., 149, 1-3, 45-58 (1996) · Zbl 0844.05078
[9] Ding, G.; Oporowski, B.; Oxley, J., On infinite antichains of matroids, J. Combin. Theory Ser. B, 63, 1, 21-40 (1995) · Zbl 0820.05013
[10] Dirac, G. A., Some theorems on abstract graphs, Proc. Lond. Math. Soc. (3), 2, 69-81 (1952) · Zbl 0047.17001
[11] Dittmann, J.; Oporowski, B., Unavoidable minors of graphs of large type, Discrete Math., 248, 1-3, 27-67 (2002) · Zbl 1038.05056
[12] Ganian, R.; Hliněný, P.; Nešetřil, J.; Obdržálek, J.; Ossona de Mendez, P., Shrub-depth: Capturing height of dense graphs, Log. Methods Comput. Sci., 15, 1 (2019), Paper No. 7 · Zbl 1515.03150
[13] Geelen, J. F.; Gerards, A. M.H.; Whittle, G., Branch-width and well-quasi-ordering in matroids and graphs, J. Combin. Theory Ser. B, 84, 2, 270-290 (2002) · Zbl 1037.05013
[14] Geelen, J.; Gerards, B.; Whittle, G., Matroid \(T\)-connectivity, SIAM J. Discrete Math., 20, 3, 588-596 (2006), (electronic) · Zbl 1122.05023
[15] Hicks, I. V.; McMurray, N. B., The branchwidth of graphs and their cycle matroids, J. Combin. Theory Ser. B, 97, 5, 681-692 (2007) · Zbl 1121.05026
[16] Higman, G., Ordering by divisibility in abstract algebras, Proc. Lond. Math. Soc. (3), 2, 326-336 (1952) · Zbl 0047.03402
[17] Hliněný, P., Branch-width, parse trees, and monadic second-order logic for matroids, J. Combin. Theory Ser. B, 96, 3, 325-351 (2006) · Zbl 1088.05022
[18] Hliněný, P.; Kwon, O.; Obdržálek, J.; Ordyniak, S., Tree-depth and vertex-minors, European J. Combin., 56, 46-56 (2016) · Zbl 1335.05168
[19] Hliněný, P.; Oum, S., Finding branch-decompositions and rank-decompositions, SIAM J. Comput., 38, 3, 1012-1032 (2008) · Zbl 1163.05331
[20] Hliněný, P.; Whittle, G., Matroid tree-width, European J. Combin., 27, 7, 1117-1128 (2006) · Zbl 1103.05019
[21] Jeong, J.; Kim, E. J.; Oum, S., Finding branch-decompositions of matroids, hypergraphs, and more, (Proc. 45th Int. Coll. on Automata, Languages and Programming, ICALP 2018, Vol. 80 (2018)), 14 · Zbl 1499.68277
[22] Jeong, J.; Kim, E. J.; Oum, S., Finding branch-decompositions of matroids, hypergraphs, and more (2019), submitted for publication
[23] Kardoš, F.; Král’, D.; Liebenau, A.; Mach, L., First order convergence of matroids, European J. Combin., 59, 150-168 (2017) · Zbl 1348.05049
[24] Kwon, O.; McCarty, R.; Oum, S.; Wollan, P., Obstructions for bounded shrub-depth and rank-depth (2019), submitted for publication
[25] Lemos, M.; Oxley, J., A sharp bound on the size of a connected matroid, Trans. Amer. Math. Soc., 353, 10, 4039-4056 (2001) · Zbl 0971.05034
[26] Mazoit, F.; Thomassé, S., Branchwidth of graphic matroids, (Hilton, A.; Talbot, J., Surveys in Combinatorics 2007. Surveys in Combinatorics 2007, London Math. Soc. Lecture Note Ser., vol. 346 (2007), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 275-286 · Zbl 1130.05017
[27] 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
[28] Oum, S., Rank-width and vertex-minors, J. Combin. Theory Ser. B, 95, 1, 79-100 (2005) · Zbl 1070.05023
[29] Oum, S., Rank-width is less than or equal to branch-width, J. Graph Theory, 57, 3, 239-244 (2008) · Zbl 1135.05059
[30] Oum, S.; Seymour, P., Approximating clique-width and branch-width, J. Combin. Theory Ser. B, 96, 4, 514-528 (2006) · Zbl 1114.05022
[31] Oxley, J., Matroid Theory, Oxford Graduate Texts in Mathematics (2011), Oxford University Press: Oxford University Press Oxford · Zbl 1254.05002
[32] Robertson, N.; Seymour, P., Graph minors—a survey, (Surveys in Combinatorics 1985 (Glasgow, 1985). Surveys in Combinatorics 1985 (Glasgow, 1985), London Math. Soc. Lecture Note Ser., vol. 103 (1985), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 153-171 · Zbl 0568.05025
[33] Robertson, N.; Seymour, P., Graph minors. X. Obstructions to tree-decomposition, J. Combin. Theory Ser. B, 52, 2, 153-190 (1991) · Zbl 0764.05069
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.