{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T17:29:03Z","timestamp":1780421343001,"version":"3.54.1"},"reference-count":66,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2015,4,23]],"date-time":"2015-04-23T00:00:00Z","timestamp":1429747200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2015,11]]},"DOI":"10.1007\/s00373-015-1569-7","type":"journal-article","created":{"date-parts":[[2015,4,22]],"date-time":"2015-04-22T08:01:40Z","timestamp":1429689700000},"page":"1941-1963","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["On Low Tree-Depth Decompositions"],"prefix":"10.1007","volume":"31","author":[{"given":"Jaroslav","family":"Ne\u0161et\u0159il","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patrice","family":"Ossona\u00a0de\u00a0Mendez","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,4,23]]},"reference":[{"issue":"5+ 6","key":"1569_CR1","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1017\/S0963548303005741","volume":"12","author":"N Alon","year":"2003","unstructured":"Alon, N., Krivelevich, M., Sudakov, B.: Tur\u00e1n numbers of bipartite graphs and related ramsey-type questions. Comb. Probab. Comput. 12(5+ 6), 477\u2013494 (2003)","journal-title":"Comb. Probab. Comput."},{"key":"1569_CR2","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/BF01305230","volume":"12","author":"N Alon","year":"1992","unstructured":"Alon, N., McDiarmid, C., Reed, B.: Star arboricity. Combinatorica 12, 375\u2013380 (1992)","journal-title":"Combinatorica"},{"key":"1569_CR3","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF02762708","volume":"94","author":"N Alon","year":"1994","unstructured":"Alon, N., Mohar, B., Sanders, D.: On acyclic colorings of graphs on surfaces. Israel J. Math. 94, 273\u2013283 (1994)","journal-title":"Israel J. Math."},{"issue":"4","key":"1569_CR4","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"1569_CR5","unstructured":"Atminas, A., Lozin, V., Razgon, I.: Well-quasi-ordering, tree-width and subquadratic properties of graphs. arxiv:1410.3260v1 (2014)"},{"key":"1569_CR6","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., Deogun, J., Jansen, K., Kloks, T., Kratsch, D., M\u00fcller, H., Tuza, Z.: Rankings of graphs. In: Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 903\/1995, pp. 292\u2013304. Springer, Berlin (1995). doi: 10.1007\/3-540-59071-4","DOI":"10.1007\/3-540-59071-4"},{"issue":"3","key":"1569_CR7","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0012-365X(79)90077-3","volume":"25","author":"O Borodin","year":"1979","unstructured":"Borodin, O.: On acyclic colorings of planar graphs. Discrete Math. 25(3), 211\u2013236 (1979)","journal-title":"Discrete Math."},{"key":"1569_CR8","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0304-3975(91)90020-3","volume":"86","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci. 86, 243\u2013266 (1991). doi: 10.1016\/0304-3975(91)90020-3","journal-title":"Theor. Comput. Sci."},{"key":"1569_CR9","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symbolic Comput. 9, 251\u2013280 (1990)","journal-title":"J. Symbolic Comput."},{"key":"1569_CR10","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: recognizable sets of finite graphs. Inform. Comput. 85, 12\u201375 (1990)","journal-title":"Inform. Comput."},{"key":"1569_CR11","unstructured":"Dawar, A., Kreutzer, S.: Parametrized complexity of first-order logic. Tech. Rep. 131, Electronic Colloquium on Computational Complexity (2009)"},{"key":"1569_CR12","doi-asserted-by":"crossref","unstructured":"Deogun, J., Kloks, T., Kratsch, D., M\u00fcller, 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\u2013758. Springer, Berlin (1994)","DOI":"10.1007\/3-540-57785-8_187"},{"key":"1569_CR13","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.jctb.2003.09.001","volume":"91","author":"M DeVos","year":"2004","unstructured":"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\u201341 (2004)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"5","key":"1569_CR14","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1002\/jgt.3190160509","volume":"16","author":"G Ding","year":"1992","unstructured":"Ding, G.: Subgraphs and well-quasi-ordering. J. Graph Theory 16(5), 489\u2013502 (1992)","journal-title":"J. Graph Theory"},{"key":"1569_CR15","unstructured":"Dvo\u0159\u00e1k, Z.: Asymptotical structure of combinatorial objects. Ph.D. thesis, Charles University, Faculty of Mathematics and Physics (2007)"},{"issue":"5","key":"1569_CR16","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1016\/j.ejc.2011.09.014","volume":"33","author":"Z Dvo\u0159\u00e1k","year":"2012","unstructured":"Dvo\u0159\u00e1k, Z., Giannopoulou, A., Thilikos, D.: Forbidden graphs for tree-depth. Eur. J. Combin. 33(5), 969\u2013979 (2012). doi: 10.1016\/j.ejc.2011.09.014 . (EuroComb \u201909)","journal-title":"Eur. J. Combin."},{"key":"1569_CR17","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1\u013e, D., Thomas, R.: Testing first-order properties for subclasses of sparse graphs. J. ACM 60, 5 Article 36 (2013). doi: 10.1145\/2499483","DOI":"10.1145\/2499483"},{"issue":"4","key":"1569_CR18","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1307\/mmj\/1028998975","volume":"10","author":"L Eggan","year":"1963","unstructured":"Eggan, L.: Transition graphs and the star-height of regular events. Mich. Math. J. 10(4), 385\u2013397 (1963)","journal-title":"Mich. Math. J."},{"key":"1569_CR19","doi-asserted-by":"crossref","unstructured":"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\u2013274 (2012). doi: 10.1109\/LICS.2012.37","DOI":"10.1109\/LICS.2012.37"},{"key":"1569_CR20","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. In: Proc. 6th Symp. Discrete Algorithms, pp. 632\u2013640. ACM and SIAM (1995)"},{"issue":"3","key":"1569_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00014","volume":"3","author":"D Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3(3), 1\u201327 (1999)","journal-title":"J. Graph Algorithms Appl."},{"key":"1569_CR22","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27, 275\u2013291 (2000). doi: 10.1007\/s004530010020 (special issue on treewidth, graph minors, and algorithms)","DOI":"10.1007\/s004530010020"},{"key":"1569_CR23","unstructured":"Erd\u0151s, P., Rubin, A., Taylor, H.: Choosability in graphs. In: Proc. West-Coast Conference on Combinatorics, Graph Theory and Computing, vol. XXVI, pp. 125\u2013157, Arcata (1979)"},{"key":"1569_CR24","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1090\/S0002-9904-1946-08715-7","volume":"52","author":"P Erd\u00f6s","year":"1946","unstructured":"Erd\u00f6s, P., Stone, A.: On the structure of linear graphs. Bull. Am. Math. Soc 52, 1087\u20131091 (1946)","journal-title":"Bull. Am. Math. Soc"},{"key":"1569_CR25","doi-asserted-by":"crossref","first-page":"2045","DOI":"10.1016\/j.dam.2011.07.017","volume":"159","author":"F Fiorenzi","year":"2011","unstructured":"Fiorenzi, F., Ochem, P., Ossona de Mendez, P., Zhu, X.: Thue choosability of trees. Discrete Appl. Math. 159, 2045\u20132049 (2011). doi: 10.1016\/j.dam.2011.07.017","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"1569_CR26","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.apal.2004.01.007","volume":"130","author":"M Frick","year":"2004","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130(1\u20133), 3\u201331 (2004). doi: 10.1016\/j.apal.2004.01.007","journal-title":"Ann. Pure Appl. Logic"},{"key":"1569_CR27","unstructured":"Gajarsk\u00fd, J., Hlin\u011bn\u00fd, 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)"},{"key":"1569_CR28","doi-asserted-by":"crossref","unstructured":"Gajarsk\u00fd, J., Hlin\u011bn\u00fd, P.: Kernelizing mso properties of trees of fixed height, and some consequences. arXiv:1204.5194 [cs.DM] (2012) (revised Jan 2014)","DOI":"10.2168\/LMCS-11(1:19)2015"},{"key":"1569_CR29","doi-asserted-by":"crossref","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Ne\u0161et\u0159il, J., Obdr\u017e\u00e1lek, J., Ossona de Mendez, P., Ramadurai, R.: When trees grow low: shrubs and fast $$\\text{ MSO }_1$$ MSO 1 . In: MFCS 2012, Lecture Notes in Computer Science, vol. 7464, pp. 419\u2013430. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-32589-2_38"},{"issue":"15","key":"1569_CR30","doi-asserted-by":"crossref","first-page":"2089","DOI":"10.1016\/j.dam.2012.03.015","volume":"160","author":"A Giannopoulou","year":"2012","unstructured":"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\u20132097 (2012). doi: 10.1016\/j.dam.2012.03.015","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1569_CR31","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0012-365X(78)90178-4","volume":"24","author":"M Golumbic","year":"1978","unstructured":"Golumbic, M.: Trivially perfect graphs. Discrete Math. 24(1), 105\u2013107 (1978). doi: 10.1016\/0012-365X(78)90178-4","journal-title":"Discrete Math."},{"key":"1569_CR32","doi-asserted-by":"crossref","unstructured":"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 \u201914, pp. 89\u201398. ACM, New York (2014). doi: 10.1145\/2591796.2591851","DOI":"10.1145\/2591796.2591851"},{"key":"1569_CR33","doi-asserted-by":"crossref","unstructured":"Gruber, H., Holzer, M.: Finite automata, digraph connectivity, and regular expression size. In: L. Aceto, I. Damg\u00e5rd, L. Goldberg, M. Halld\u00f3rsson, A. Ing\u00f3lfsdttir, I. Walukiewicz (eds.) Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 5126, pp. 39\u201350. Springer, Berlin (2008). doi: 10.1007\/978-3-540-70583-3_4","DOI":"10.1007\/978-3-540-70583-3_4"},{"key":"1569_CR34","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Golovach, P.: Choosability of $$P_5$$ P 5 -free graphs. In: Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 5734, pp. 382\u2013391. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-03816-7_33"},{"key":"1569_CR35","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications","author":"P Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications, vol. 28. Oxford University Press, Oxford (2004)"},{"key":"1569_CR36","doi-asserted-by":"crossref","unstructured":"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\u2013228. Springer, Berlin (2011). doi: 10.1007\/978-3-642-22953-4_19","DOI":"10.1007\/978-3-642-22953-4_19"},{"key":"1569_CR37","volume-title":"Graph Coloring Problems","author":"T Jensen","year":"2011","unstructured":"Jensen, T., Toft, B.: Graph Coloring Problems, vol. 39. Wiley, New York (2011)"},{"key":"1569_CR38","doi-asserted-by":"crossref","unstructured":"Jiang, T.: Compact topological minors in graphs. J. Graph Theory (2010). doi: 10.1002\/jgt.20522 (published online)","DOI":"10.1002\/jgt.20522"},{"key":"1569_CR39","doi-asserted-by":"crossref","unstructured":"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\u201320 (2013)","DOI":"10.1145\/2463664.2463667"},{"key":"1569_CR40","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1023\/B:ORDE.0000026489.93166.cb","volume":"20","author":"H Kierstead","year":"2003","unstructured":"Kierstead, H., Yang, D.: Orderings on graphs and game coloring number. Order 20, 255\u2013264 (2003)","journal-title":"Order"},{"issue":"1","key":"1569_CR41","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s00493-004-0010-2","volume":"24","author":"D K\u00fchn","year":"2004","unstructured":"K\u00fchn, D., Osthus, D.: Every graph of sufficiently large average degree contains a $$C_4$$ C 4 -free subgraph of large average degree. Combinatorica 24(1), 155\u2013162 (2004)","journal-title":"Combinatorica"},{"key":"1569_CR42","doi-asserted-by":"crossref","unstructured":"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\u2013683. Springer, Berlin (2013). doi: 10.1007\/978-3-642-39206-1_57","DOI":"10.1007\/978-3-642-39206-1_57"},{"issue":"3","key":"1569_CR43","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1016\/j.jctb.2006.07.001","volume":"97","author":"R Naserasr","year":"2007","unstructured":"Naserasr, R.: Homomorphisms and edge-coloring of planar graphs. J. Combin. Theory Ser. B 97(3), 394\u2013400 (2007). doi: 10.1016\/j.jctb.2006.07.001","journal-title":"J. Combin. Theory Ser. B"},{"issue":"18","key":"1569_CR44","doi-asserted-by":"crossref","first-page":"5789","DOI":"10.1016\/j.disc.2009.04.032","volume":"309","author":"R Naserasr","year":"2009","unstructured":"Naserasr, R., Nigussie, Y., \u0160krekovski, R.: Homomorphisms of triangle-free graphs without a $$K_5$$ K 5 -minor. Discrete Math. 309(18), 5789\u20135798 (2009). doi: 10.1016\/j.disc.2009.04.032","journal-title":"Discrete Math."},{"key":"1569_CR45","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, 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\u2013664. Discrete and Computational Geometry (2003)","DOI":"10.1007\/978-3-642-55566-4_29"},{"key":"1569_CR46","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Linear time low tree-width partitions and algorithmic consequences. In: STOC\u201906. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 391\u2013400. ACM Press (2006). doi: 10.1145\/1132516.1132575","DOI":"10.1145\/1132516.1132575"},{"issue":"6","key":"1569_CR47","doi-asserted-by":"crossref","first-page":"1022","DOI":"10.1016\/j.ejc.2005.01.010","volume":"27","author":"J Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Tree depth, subgraph coloring and homomorphism bounds. Eur. J. Combin. 27(6), 1022\u20131041 (2006). doi: 10.1016\/j.ejc.2005.01.010","journal-title":"Eur. J. Combin."},{"issue":"3","key":"1569_CR48","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1016\/j.ejc.2006.07.013","volume":"29","author":"J Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. Decompositions. Eur. J. Combin. 29(3), 760\u2013776 (2008). doi: 10.1016\/j.ejc.2006.07.013","journal-title":"Eur. J. Combin."},{"issue":"3","key":"1569_CR49","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1016\/j.ejc.2006.07.014","volume":"29","author":"J Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Grad and classes with bounded expansion II. Algorithmic aspects. Eur. J. Combin. 29(3), 777\u2013791 (2008). doi: 10.1016\/j.ejc.2006.07.014","journal-title":"Eur. J. Combin."},{"issue":"4","key":"1569_CR50","doi-asserted-by":"crossref","first-page":"1012","DOI":"10.1016\/j.ejc.2007.11.019","volume":"29","author":"J Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Grad and classes with bounded expansion III. Restricted graph homomorphism dualities. Eur. J. Combin. 29(4), 1012\u20131024 (2008). doi: 10.1016\/j.ejc.2007.11.019","journal-title":"Eur. J. Combin."},{"issue":"7","key":"1569_CR51","doi-asserted-by":"crossref","first-page":"1126","DOI":"10.1016\/j.ejc.2011.03.007","volume":"32","author":"J Ne\u0161et\u0159il","year":"2011","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: How many F\u2019s are there in G? Eur. J. Combin. 32(7), 1126\u20131141 (2011). doi: 10.1016\/j.ejc.2011.03.007","journal-title":"Eur. J. Combin."},{"issue":"4","key":"1569_CR52","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1016\/j.ejc.2011.01.006","volume":"32","author":"J Ne\u0161et\u0159il","year":"2011","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: On nowhere dense graphs. Eur. J. Combin. 32(4), 600\u2013617 (2011). doi: 10.1016\/j.ejc.2011.01.006","journal-title":"Eur. J. Combin."},{"key":"1569_CR53","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity (Graphs, Structures, and Algorithms), Algorithms and Combinatorics, vol. 28. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-27875-4"},{"key":"1569_CR54","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: On first-order definable colorings. In: Ne\u0161et\u0159il, J., Pellegrini, M. (eds.) Geometry, Structure and Randomness in Combinatorics, Publications of the Scuola Normale Superiore, CRM Series, vol. 18, pp. 99\u2013122. Edizioni della Normale (2015)","DOI":"10.1007\/978-88-7642-525-7_6"},{"issue":"2","key":"1569_CR55","first-page":"415","volume":"26","author":"J Ne\u0161et\u0159il","year":"1985","unstructured":"Ne\u0161et\u0159il, J., Poljak, S.: Complexity of the subgraph problem. Comment Math. Univ. Carol. 26(2), 415\u2013420 (1985)","journal-title":"Comment Math. Univ. Carol."},{"issue":"6","key":"1569_CR56","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1016\/S0195-6698(03)00064-7","volume":"24","author":"J Ne\u0161et\u0159il","year":"2003","unstructured":"Ne\u0161et\u0159il, J., Shelah, S.: On the order of countable graphs. Eur. J. Combin. 24(6), 649\u2013663 (2003). doi: 10.1016\/S0195-6698(03)00064-7","journal-title":"Eur. J. Combin."},{"key":"1569_CR57","doi-asserted-by":"crossref","unstructured":"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\u201329 (1991)","DOI":"10.1007\/3-540-53832-1_28"},{"key":"1569_CR58","unstructured":"Plotkin, S., Rao, S., Smith, W.: Shallow excluded minors and improved graph decomposition. In: 5th Symp. Discrete Algorithms, pp. 462\u2013470. SIAM (1994)"},{"issue":"3","key":"1569_CR59","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1379759.1379763","volume":"55","author":"B Rossman","year":"2008","unstructured":"Rossman, B.: Homomorphism preservation theorems. J. ACM 55(3), 1\u201353 (2008). doi: 10.1145\/1379759.1379763","journal-title":"J. ACM"},{"issue":"3","key":"1569_CR60","first-page":"2","volume":"6","author":"E Sampathkumar","year":"1977","unstructured":"Sampathkumar, E.: $$D_n$$ D n -colorings of planar graphs. Graph Theory Newslett. 6(3), 2 (1977). (abstract)","journal-title":"Graph Theory Newslett."},{"key":"1569_CR61","doi-asserted-by":"crossref","unstructured":"Sch\u00e4ffer, A.: Optimal node ranking of trees in linear time. Inform. Process. Lett. 33, 91\u201396 (1989\/1990)","DOI":"10.1016\/0020-0190(89)90161-0"},{"key":"1569_CR62","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"P Seymour","year":"1993","unstructured":"Seymour, P., Thomas, R.: Graph searching and a min\u2013max theorem for tree-width. J. Combin. Theory Ser. B 58, 22\u201333 (1993)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"1569_CR63","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1006\/jctb.1994.1052","volume":"62","author":"C Thomassen","year":"1994","unstructured":"Thomassen, C.: Five-coloring graphs on the torus. J. Combin. Theory Ser. B 62(1), 11\u201333 (1994). doi: 10.1006\/jctb.1994.1052","journal-title":"J. Combin. Theory Ser. B"},{"key":"1569_CR64","first-page":"3","volume":"29","author":"V Vizing","year":"1976","unstructured":"Vizing, V.: Coloring the vertices of a graph in prescribed colors. Metody Diskretnogo Analiza v Teorii Kodov i Schem 29, 3\u201310 (1976). (in Russian)","journal-title":"Metody Diskretnogo Analiza v Teorii Kodov i Schem"},{"key":"1569_CR65","unstructured":"Wikipedia contributors: Tree-depth. Wikipedia, The Free Encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Tree-depth&oldid=618790044 . Accessed 8 Nov 2014"},{"issue":"18","key":"1569_CR66","doi-asserted-by":"crossref","first-page":"5562","DOI":"10.1016\/j.disc.2008.03.024","volume":"309","author":"X Zhu","year":"2009","unstructured":"Zhu, X.: Colouring graphs with bounded generalized colouring number. Discrete Math. 309(18), 5562\u20135568 (2009). doi: 10.1016\/j.disc.2008.03.024","journal-title":"Discrete Math."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-015-1569-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-015-1569-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-015-1569-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,23]],"date-time":"2019-08-23T19:14:12Z","timestamp":1566587652000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-015-1569-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,23]]},"references-count":66,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["1569"],"URL":"https:\/\/doi.org\/10.1007\/s00373-015-1569-7","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,23]]}}}