×

On low tree-depth decompositions. (English) Zbl 1327.05279

Summary: The theory of sparse structures usually uses tree like structures as building blocks. In the context of sparse/dense dichotomy this role is played by graphs with bounded tree-depth. In this paper we survey results related to this concept and particularly explain how these graphs are used to decompose and construct more complex graphs and structures. In more technical terms we survey some of the properties and applications of low tree-depth decomposition of graphs.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs
05C85 Graph algorithms (graph-theoretic aspects)
05C42 Density (toughness, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N., Krivelevich, M., Sudakov, B.: Turán numbers of bipartite graphs and related ramsey-type questions. Comb. Probab. Comput. 12(5+ 6), 477-494 (2003) · Zbl 1060.05050 · doi:10.1017/S0963548303005741
[2] Alon, N., McDiarmid, C., Reed, B.: Star arboricity. Combinatorica 12, 375-380 (1992) · Zbl 0780.05043 · doi:10.1007/BF01305230
[3] Alon, N., Mohar, B., Sanders, D.: On acyclic colorings of graphs on surfaces. Israel J. Math. 94, 273-283 (1994) · Zbl 0857.05033 · doi:10.1007/BF02762708
[4] Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844-856 (1995) · Zbl 0885.68116 · doi:10.1145/210332.210337
[5] Atminas, A., Lozin, V., Razgon, I.: Well-quasi-ordering, tree-width and subquadratic properties of graphs. arxiv:1410.3260v1 (2014) · Zbl 0571.05050
[6] Bodlaender, H., Deogun, J., Jansen, K., Kloks, T., Kratsch, D., Müller, H., Tuza, Z.: Rankings of graphs. In: Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 903/1995, pp. 292-304. Springer, Berlin (1995). doi:10.1007/3-540-59071-4 · Zbl 0907.68137
[7] Borodin, O.: On acyclic colorings of planar graphs. Discrete Math. 25(3), 211-236 (1979) · Zbl 0406.05031 · doi:10.1016/0012-365X(79)90077-3
[8] Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci. 86, 243-266 (1991). doi:10.1016/0304-3975(91)90020-3 · Zbl 0735.68015 · doi:10.1016/0304-3975(91)90020-3
[9] Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symbolic Comput. 9, 251-280 (1990) · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2
[10] Courcelle, B.: The monadic second-order logic of graphs I: recognizable sets of finite graphs. Inform. Comput. 85, 12-75 (1990) · Zbl 0722.03008 · doi:10.1016/0890-5401(90)90043-H
[11] Dawar, A., Kreutzer, S.: Parametrized complexity of first-order logic. Tech. Rep. 131, Electronic Colloquium on Computational Complexity (2009) · Zbl 1248.68241
[12] Deogun, J., Kloks, T., Kratsch, D., Müller, H.: On vertex ranking for permutation and other graphs. In: Enjalbert, P., Mayr, E., Wagner, K. (eds.) Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 775, pp. 747-758. Springer, Berlin (1994) · Zbl 0941.05516
[13] DeVos, M., Ding, G., Oporowski, B., Sanders, D., Reed, B., Seymour, P., Vertigan, D.: Excluding any graph as a minor allows a low tree-width 2-coloring. J. Combin. Theory Ser. B 91, 25-41 (2004) · Zbl 1042.05036 · doi:10.1016/j.jctb.2003.09.001
[14] Ding, G.: Subgraphs and well-quasi-ordering. J. Graph Theory 16(5), 489-502 (1992) · Zbl 0762.05093 · doi:10.1002/jgt.3190160509
[15] Dvořák, Z.: Asymptotical structure of combinatorial objects. Ph.D. thesis, Charles University, Faculty of Mathematics and Physics (2007)
[16] Dvořák, Z., Giannopoulou, A., Thilikos, D.: Forbidden graphs for tree-depth. Eur. J. Combin. 33(5), 969-979 (2012). doi:10.1016/j.ejc.2011.09.014. (EuroComb ’09) · Zbl 1239.05062 · doi:10.1016/j.ejc.2011.09.014
[17] Dvořák, Z., Kráľ, D., Thomas, R.: Testing first-order properties for subclasses of sparse graphs. J. ACM 60, 5 Article 36 (2013). doi:10.1145/2499483 · Zbl 1281.05114
[18] Eggan, L.: Transition graphs and the star-height of regular events. Mich. Math. J. 10(4), 385-397 (1963) · Zbl 0173.01504 · doi:10.1307/mmj/1028998975
[19] Elberfeld, M., Grohe, M., Tantau, T.: Where first-order and monadic second-order logic coincide. In: Logic in Computer Science (LICS), 2012 27th Annual IEEE Symposium on, pp. 265-274 (2012). doi:10.1109/LICS.2012.37 · Zbl 1364.03015
[20] Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. In: Proc. 6th Symp. Discrete Algorithms, pp. 632-640. ACM and SIAM (1995) · Zbl 0858.05075
[21] Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3(3), 1-27 (1999) · Zbl 0949.05055 · doi:10.7155/jgaa.00014
[22] Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27, 275-291 (2000). doi:10.1007/s004530010020 (special issue on treewidth, graph minors, and algorithms) · Zbl 0963.05128
[23] Erdős, P., Rubin, A., Taylor, H.: Choosability in graphs. In: Proc. West-Coast Conference on Combinatorics, Graph Theory and Computing, vol. XXVI, pp. 125-157, Arcata (1979) · Zbl 1239.05064
[24] Erdös, P., Stone, A.: On the structure of linear graphs. Bull. Am. Math. Soc 52, 1087-1091 (1946) · Zbl 0063.01277 · doi:10.1090/S0002-9904-1946-08715-7
[25] Fiorenzi, F., Ochem, P., Ossona de Mendez, P., Zhu, X.: Thue choosability of trees. Discrete Appl. Math. 159, 2045-2049 (2011). doi:10.1016/j.dam.2011.07.017 · Zbl 1239.05064 · doi:10.1016/j.dam.2011.07.017
[26] Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130(1-3), 3-31 (2004). doi:10.1016/j.apal.2004.01.007 · Zbl 1062.03032 · doi:10.1016/j.apal.2004.01.007
[27] Gajarský, J., Hliněný, P.: Faster deciding MSO properties of trees of fixed height, and some consequences. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 18. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2012) · Zbl 1354.68122
[28] Gajarský, J., Hliněný, P.: Kernelizing mso properties of trees of fixed height, and some consequences. arXiv:1204.5194 [cs.DM] (2012) (revised Jan 2014) · Zbl 1354.68122
[29] Ganian, R., Hliněný, P., Nešetřil, J., Obdržálek, J., Ossona de Mendez, P., Ramadurai, R.: When trees grow low: shrubs and fast \[\text{ MSO }_1\] MSO1. In: MFCS 2012, Lecture Notes in Computer Science, vol. 7464, pp. 419-430. Springer, Berlin (2012) · Zbl 1365.68323
[30] Giannopoulou, A., Thilikos, D.: LIFO-search: a minmax theorem and a searching game for cycle-rank and tree-depth. Discrete Appl. Math. 160(15), 2089-2097 (2012). doi:10.1016/j.dam.2012.03.015 · Zbl 1250.91019 · doi:10.1016/j.dam.2012.03.015
[31] Golumbic, M.: Trivially perfect graphs. Discrete Math. 24(1), 105-107 (1978). doi:10.1016/0012-365X(78)90178-4 · Zbl 0384.05057 · doi:10.1016/0012-365X(78)90178-4
[32] Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC ’14, pp. 89-98. ACM, New York (2014). doi:10.1145/2591796.2591851 · Zbl 1315.05118
[33] Gruber, H., Holzer, M.: Finite automata, digraph connectivity, and regular expression size. In: L. Aceto, I. Damgård, L. Goldberg, M. Halldórsson, A. Ingólfsdttir, I. Walukiewicz (eds.) Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 5126, pp. 39-50. Springer, Berlin (2008). doi:10.1007/978-3-540-70583-3_4 · Zbl 1155.68418
[34] Heggernes, P., Golovach, P.: Choosability of \[P_5\] P5-free graphs. In: Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 5734, pp. 382-391. Springer, Berlin (2009) · Zbl 1250.68127
[35] Hell, P., Nešetřil, J.: Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications, vol. 28. Oxford University Press, Oxford (2004) · Zbl 1062.05139 · doi:10.1093/acprof:oso/9780198528173.001.0001
[36] Hunter, P.: LIFO-search on digraphs: a searching game for cycle-rank. In: Owe, O., Steffen, M., Telle, J.A. (eds.) Fundamentals of Computation Theory, Lecture Notes in Computer Science, vol. 6914, pp. 217-228. Springer, Berlin (2011). doi:10.1007/978-3-642-22953-4_19 · Zbl 1342.05088
[37] Jensen, T., Toft, B.: Graph Coloring Problems, vol. 39. Wiley, New York (2011)
[38] Jiang, T.: Compact topological minors in graphs. J. Graph Theory (2010). doi:10.1002/jgt.20522 (published online) · Zbl 1060.05050
[39] Kazana, W., Segoufin, L.: Enumeration of first-order queries on classes of structures with bounded expansion. In: Proceedings of the 16th International Conference on Database Theory, pp. 10-20 (2013) · Zbl 1353.68068
[40] Kierstead, H., Yang, D.: Orderings on graphs and game coloring number. Order 20, 255-264 (2003) · Zbl 1041.05029 · doi:10.1023/B:ORDE.0000026489.93166.cb
[41] Kühn, D., Osthus, D.: Every graph of sufficiently large average degree contains a \[C_4\] C4-free subgraph of large average degree. Combinatorica 24(1), 155-162 (2004) · Zbl 1047.05022 · doi:10.1007/s00493-004-0010-2
[42] Lampis, M.: Model checking lower bounds for simple graphs. In: Fomin, F., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) Automata, Languages, and Programming, Lecture Notes in Computer Science, vol. 7965, pp. 673-683. Springer, Berlin (2013). doi:10.1007/978-3-642-39206-1_57 · Zbl 1336.68165
[43] Naserasr, R.: Homomorphisms and edge-coloring of planar graphs. J. Combin. Theory Ser. B 97(3), 394-400 (2007). doi:10.1016/j.jctb.2006.07.001 · Zbl 1116.05032 · doi:10.1016/j.jctb.2006.07.001
[44] Naserasr, R., Nigussie, Y., Škrekovski, R.: Homomorphisms of triangle-free graphs without a \[K_5\] K5-minor. Discrete Math. 309(18), 5789-5798 (2009). doi:10.1016/j.disc.2009.04.032 · Zbl 1210.05084 · doi:10.1016/j.disc.2009.04.032
[45] Nešetřil, J., Ossona de Mendez, P.: Colorings and homomorphisms of minor closed classes. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) The Goodman-Pollack Festschrift, Algorithms and Combinatorics, vol. 25, pp. 651-664. Discrete and Computational Geometry (2003) · Zbl 1071.05526
[46] Nešetřil, J., Ossona de Mendez, P.: Linear time low tree-width partitions and algorithmic consequences. In: STOC’06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 391-400. ACM Press (2006). doi:10.1145/1132516.1132575 · Zbl 1301.05268
[47] Nešetřil, J., Ossona de Mendez, P.: Tree depth, subgraph coloring and homomorphism bounds. Eur. J. Combin. 27(6), 1022-1041 (2006). doi:10.1016/j.ejc.2005.01.010 · Zbl 1089.05025 · doi:10.1016/j.ejc.2005.01.010
[48] Nešetřil, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. Decompositions. Eur. J. Combin. 29(3), 760-776 (2008). doi:10.1016/j.ejc.2006.07.013 · Zbl 1156.05056 · doi:10.1016/j.ejc.2006.07.013
[49] Nešetřil, J., Ossona de Mendez, P.: Grad and classes with bounded expansion II. Algorithmic aspects. Eur. J. Combin. 29(3), 777-791 (2008). doi:10.1016/j.ejc.2006.07.014 · Zbl 1185.05131 · doi:10.1016/j.ejc.2006.07.014
[50] Nešetřil, J., Ossona de Mendez, P.: Grad and classes with bounded expansion III. Restricted graph homomorphism dualities. Eur. J. Combin. 29(4), 1012-1024 (2008). doi:10.1016/j.ejc.2007.11.019 · Zbl 1213.05240 · doi:10.1016/j.ejc.2007.11.019
[51] Nešetřil, J., Ossona de Mendez, P.: How many F’s are there in G? Eur. J. Combin. 32(7), 1126-1141 (2011). doi:10.1016/j.ejc.2011.03.007 · Zbl 1229.05212 · doi:10.1016/j.ejc.2011.03.007
[52] Nešetřil, J., Ossona de Mendez, P.: On nowhere dense graphs. Eur. J. Combin. 32(4), 600-617 (2011). doi:10.1016/j.ejc.2011.01.006 · Zbl 1226.05102 · doi:10.1016/j.ejc.2011.01.006
[53] Nešetřil, J., Ossona de Mendez, P.: Sparsity (Graphs, Structures, and Algorithms), Algorithms and Combinatorics, vol. 28. Springer, Berlin (2012) · Zbl 1268.05002
[54] Nešetřil, J., Ossona de Mendez, P.: On first-order definable colorings. In: Nešetřil, J., Pellegrini, M. (eds.) Geometry, Structure and Randomness in Combinatorics, Publications of the Scuola Normale Superiore, CRM Series, vol. 18, pp. 99-122. Edizioni della Normale (2015) · Zbl 1326.05049
[55] Nešetřil, J., Poljak, S.: Complexity of the subgraph problem. Comment Math. Univ. Carol. 26(2), 415-420 (1985) · Zbl 0571.05050
[56] Nešetřil, J., Shelah, S.: On the order of countable graphs. Eur. J. Combin. 24(6), 649-663 (2003). doi:10.1016/S0195-6698(03)00064-7 · Zbl 1030.03028 · doi:10.1016/S0195-6698(03)00064-7
[57] Plehn, J., Voigt, B.: Finding minimally weighted subgraphs. In: Springer-Verlag (ed.) Proc. 16th Int. Workshop Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 484, pp. 18-29 (1991) · Zbl 0768.68170
[58] Plotkin, S., Rao, S., Smith, W.: Shallow excluded minors and improved graph decomposition. In: 5th Symp. Discrete Algorithms, pp. 462-470. SIAM (1994) · Zbl 0867.05069
[59] Rossman, B.: Homomorphism preservation theorems. J. ACM 55(3), 1-53 (2008). doi:10.1145/1379759.1379763 · Zbl 1326.03038 · doi:10.1145/1379759.1379763
[60] Sampathkumar, E.: \[D_n\] Dn-colorings of planar graphs. Graph Theory Newslett. 6(3), 2 (1977). (abstract)
[61] Schäffer, A.: Optimal node ranking of trees in linear time. Inform. Process. Lett. 33, 91-96 (1989/1990) · Zbl 0683.68038
[62] Seymour, P., Thomas, R.: Graph searching and a min-max theorem for tree-width. J. Combin. Theory Ser. B 58, 22-33 (1993) · Zbl 0795.05110 · doi:10.1006/jctb.1993.1027
[63] Thomassen, C.: Five-coloring graphs on the torus. J. Combin. Theory Ser. B 62(1), 11-33 (1994). doi:10.1006/jctb.1994.1052 · Zbl 0805.05022 · doi:10.1006/jctb.1994.1052
[64] Vizing, V.: Coloring the vertices of a graph in prescribed colors. Metody Diskretnogo Analiza v Teorii Kodov i Schem 29, 3-10 (1976). (in Russian)
[65] Wikipedia contributors: Tree-depth. Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=Tree-depth&oldid=618790044. Accessed 8 Nov 2014 · Zbl 1210.05084
[66] Zhu, X.: Colouring graphs with bounded generalized colouring number. Discrete Math. 309(18), 5562-5568 (2009). doi:10.1016/j.disc.2008.03.024 · Zbl 1216.05043 · doi:10.1016/j.disc.2008.03.024
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.