{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T18:30:01Z","timestamp":1781893801719,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662531730","type":"print"},{"value":"9783662531747","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_23","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T10:50:06Z","timestamp":1470307806000},"page":"325-338","source":"Crossref","is-referenced-by-count":8,"title":["Colouring and Covering Nowhere Dense Graphs"],"prefix":"10.1007","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephan","family":"Kreutzer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roman","family":"Rabinovich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Konstantinos","family":"Stavropoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Malkhi, D., Wieder, U.: Strong-diameter decompositions of minor free graphs. In: Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 16\u201324. ACM (2007)","DOI":"10.1145\/1248377.1248381"},{"key":"23_CR2","unstructured":"Dawar, A., Kreutzer, S.: Domination problems in nowhere-dense graph classes. In: Kannhan, R., Kumar, K.N. (eds.) Proceedings of the 29th Conference on Foundations of Software Technology and Theoretical Computer Science. LIPIcs, vol. 4, pp. 157\u2013168. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2009)"},{"key":"23_CR3","volume-title":"Graph Theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"issue":"1","key":"23_CR4","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s00493-005-0009-3","volume":"25","author":"R Diestel","year":"2004","unstructured":"Diestel, R., Rempel, C.: Dense minors in graphs of large girth. Combinatorica 25(1), 111\u2013116 (2004)","journal-title":"Combinatorica"},{"issue":"5","key":"23_CR5","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1016\/j.ejc.2012.12.004","volume":"34","author":"Z Dvo\u0159\u00e1k","year":"2013","unstructured":"Dvo\u0159\u00e1k, Z.: Constant-factor approximation of the domination number in sparse graphs. Eur. J. Comb. 34(5), 833\u2013840 (2013)","journal-title":"Eur. J. Comb."},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l\u2019, D., Thomas, R.: Deciding first-order properties for sparse graphs. J. ACM (2013). to appear","DOI":"10.1145\/2499483"},{"key":"23_CR7","volume-title":"Computers and Intractability","author":"MR Garey","year":"2002","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. W.H. freeman, New York (2002)"},{"key":"23_CR8","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Characterisations of nowhere dense graphs. In: Seth, A., Vishnoi, N.K. (eds.) Proceedings of the 32nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. LIPIcs, vol. 24, pp. 21\u201340. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013)"},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. In: Proceedings of the 46th ACM Symposium on Theory of Computing, pp. 89\u201398 (2014)","DOI":"10.1145\/2591796.2591851"},{"key":"23_CR10","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1090\/dimacs\/009\/08","volume":"9","author":"HA Kierstead","year":"1993","unstructured":"Kierstead, H.A., Trotter, W.T.: Planar graph coloring with an uncooperative partner. DIMACS Ser. Discrete Math. Theor. Comput. Sci. 9, 85\u201393 (1993)","journal-title":"DIMACS Ser. Discrete Math. Theor. Comput. Sci."},{"issue":"3","key":"23_CR11","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1023\/B:ORDE.0000026489.93166.cb","volume":"20","author":"HA Kierstead","year":"2003","unstructured":"Kierstead, H.A., Yang, D.: Orderings on graphs and game coloring number. Order 20(3), 255\u2013264 (2003)","journal-title":"Order"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Kreutzer, S.: Algorithmic meta-theorems. In: Esparza, J., Michaux, C., Steinhorn, C. (eds.) Finite and Algorithmic Model Theory, London Mathematical Society Lecture Note Series, chap. 5, pp. 177\u2013270. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511974960.006"},{"issue":"1","key":"23_CR13","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1090\/S0273-0979-1995-00569-0","volume":"32","author":"F Lazebnik","year":"1995","unstructured":"Lazebnik, F., Ustimenko, V.A., Woldar, A.J.: A new series of dense graphs of high girth. Bull. Am. Math. Soc. 32(1), 73\u201379 (1995)","journal-title":"Bull. Am. Math. Soc."},{"key":"23_CR14","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Characterization of nowhere dense classes and classes with bounded expansion by coverings. (to appear)"},{"key":"23_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity. Springer, Heidelberg (2012)"},{"issue":"4","key":"23_CR16","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. Comb. 32(4), 600\u2013617 (2011)","journal-title":"Eur. J. Comb."},{"key":"23_CR17","unstructured":"Peleg, D.: Distributed computing. SIAM Monogr. Discrete Math. Appl. 5 (2000)"},{"key":"23_CR18","unstructured":"Pothen, A.: The complexity of optimal elimination trees. Pennsylvania State University, Department of Computer Science (1988)"},{"issue":"1","key":"23_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM (JACM) 52(1), 1\u201324 (2005)","journal-title":"J. ACM (JACM)"},{"issue":"18","key":"23_CR20","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)","journal-title":"Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T15:57:45Z","timestamp":1498319865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}