{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T04:44:55Z","timestamp":1790397895438,"version":"4.1.0"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["648527"],"award-info":[{"award-number":["648527"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["UMO-2015\/19\/P\/ST6\/03998"],"award-info":[{"award-number":["UMO-2015\/19\/P\/ST6\/03998"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>In [M. Grohe, S. Kreutzer, and S. Siebertz, J. ACM, 64 (2017), 17] it was shown that nowhere dense classes of graphs admit sparse neighborhood covers of small degree. We show that a monotone graph class admits sparse neighborhood covers if and only if it is nowhere dense. The existence of such covers for nowhere dense classes is established through bounds on so-called weak coloring numbers. The core results of this paper are various lower and upper bounds on the weak coloring numbers and other, closely related, generalized coloring numbers. We prove tight bounds for these numbers on graphs of bounded treewidth. We clarify and tighten the relation between the density of shallow minors and the various generalized coloring numbers. These upper bounds are complemented by new, stronger exponential lower bounds on the weak and strong coloring numbers, and by superpolynomial lower bounds on the weak coloring numbers on classes of polynomial expansion. Finally, we show that computing weak $r$-coloring numbers is NP-complete for all $r\\geq 3$.<\/jats:p>","DOI":"10.1137\/18m1168753","type":"journal-article","created":{"date-parts":[[2018,10,30]],"date-time":"2018-10-30T16:57:57Z","timestamp":1540918677000},"page":"2467-2481","source":"Crossref","is-referenced-by-count":23,"title":["Coloring and Covering Nowhere Dense Graphs"],"prefix":"10.1137","volume":"32","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6347-1198","authenticated-orcid":true,"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":"351","published-online":{"date-parts":[[2018,10,30]]},"reference":[{"key":"atypb1","first-page":"16","author":"Abraham I.","year":"2007","journal-title":"New York"},{"key":"atypb2","unstructured":"A. Dawar and S. Kreutzer,\n                      Domination problems in nowhere-dense graph classes\n                      , in Proceedings of the 29th Conference on Foundations of Software Technology and Theoretical Computer Science, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik 4, 2009, pp. 157-168."},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 4th ed., Grad. Texts in Math. 173, Springer, New York, 2012.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0009-3"},{"key":"atypb5","unstructured":"Z. Dvo\u0159\u00e1k,\n                      Asymptotical structure of combinatorial objects\n                      , Ph.D. thesis, Charles University, Prague, Czech Republic, 2007."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.12.004"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/2499483"},{"key":"atypb8","first-page":"63","author":"Eickmeyer K.","year":"2017","journal-title":"Poland"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.09.003"},{"key":"atypb10","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, New York, 1979."},{"key":"atypb11","unstructured":"M. Grohe, S. Kreutzer, and S. Siebertz,\n                      Characterisations of nowhere dense graphs\n                      , in Proceedings of the 32nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik 24, 2013, pp. 21-40."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/3051095"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190180605"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1023\/B:ORDE.0000026489.93166.cb"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"S. Kreutzer,\n                      Algorithmic meta-theorems\n                      , in Finite and Algorithmic Model Theory, London Math. Soc. Lecture Note Ser., Cambridge University Press, Cambridge, UK, 2011, ch. 5, pp. 177-270.","DOI":"10.1017\/CBO9780511974960.006"},{"key":"atypb16","first-page":"1533","author":"Kreutzer S.","year":"2017","journal-title":"Philadelphia"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1995-00569-0"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"J. Ne\u0161et\u0159il and P. Ossona de Mendez,\n                      Sparsity\n                      , Springer, New York, 2012.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-015-1569-7"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"D. Peleg,\n                      Distributed Computing: A Locality-Sensitivity Approach\n                      , SIAM Monogr. Discrete Math. Appl. 5, SIAM, Philadelphia, 2000.","DOI":"10.1137\/1.9780898719772"},{"key":"atypb22","unstructured":"A. Pothen,\n                      The Complexity of Optimal Elimination Trees\n                      , Tech. report, Pennsylvania State University, Department of Computer Science, 1988."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.06.019"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.03.024"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1168753","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:53:46Z","timestamp":1787316826000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1168753"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/18M1168753"],"URL":"https:\/\/doi.org\/10.1137\/18m1168753","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}