{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:28:29Z","timestamp":1763468909477,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031433795"},{"type":"electronic","value":"9783031433801"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-43380-1_23","type":"book-chapter","created":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T20:29:12Z","timestamp":1695414552000},"page":"319-333","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Cops and\u00a0Robbers on\u00a0Multi-Layer Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0266-3292","authenticated-orcid":false,"given":"Jessica","family":"Enright","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5299-3073","authenticated-orcid":false,"given":"Kitty","family":"Meeks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0040-2088","authenticated-orcid":false,"given":"William","family":"Pettersson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6543-2934","authenticated-orcid":false,"given":"John","family":"Sylvester","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,23]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Aigner, M., Fromme, M.: A game of cops and robbers. Discret. Appl. Math. 8(1), 1\u201312 (1984)","DOI":"10.1016\/0166-218X(84)90073-8"},{"key":"23_CR2","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, Third Edition. Wiley-Interscience series in discrete mathematics and optimization. Wiley, Hoboken (2008)"},{"key":"23_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-030-54921-3_12","volume-title":"Structural Information and Communication Complexity","author":"S Balev","year":"2020","unstructured":"Balev, S., Laredo Jim\u00e9nez, J.L., Lamprou, I., Pign\u00e9, Y., Sanlaville, E.: Cops and robbers on dynamic graphs: offline and online case. In: Richa, A.W., Scheideler, C. (eds.) SIROCCO 2020. LNCS, vol. 12156, pp. 203\u2013219. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-54921-3_12"},{"key":"23_CR4","unstructured":"Bollob\u00e1s, B.: Random graphs, volume 73 of Cambridge Studies in Advanced Mathematics, second edition. Cambridge University Press, Cambridge (2001)"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Bonato, A., Nowakowski, R.J.: The Game of Cops and Robbers on Graphs. Student Mathematical Library. American Mathematical Society, New York (2011)","DOI":"10.1090\/stml\/061"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Bonato, A., Pralat, P.: Graph Searching Games and Probabilistic Methods. Discrete Mathematics and Its Applications. CRC Press, London, England, December 2017","DOI":"10.1201\/9781315212135"},{"issue":"4","key":"23_CR7","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1080\/15427951.2007.10129149","volume":"4","author":"A Bonato","year":"2007","unstructured":"Bonato, A., Pralat, P., Wang, C.: Pursuit-evasion in models of complex networks. Internet Math. 4(4), 419\u2013436 (2007)","journal-title":"Internet Math."},{"issue":"4","key":"23_CR8","doi-asserted-by":"publisher","first-page":"2459","DOI":"10.1137\/20M1312150","volume":"35","author":"NJ Bowler","year":"2021","unstructured":"Bowler, N.J., Erde, J., Lehner, F., Pitz, M.: Bounding the cop number of a graph by its genus. SIAM J. Discret. Math. 35(4), 2459\u20132489 (2021)","journal-title":"SIAM J. Discret. Math."},{"key":"23_CR9","unstructured":"Brandt, S., Pettie, S., Uitto, J.: Fine-grained lower bounds on cops and robbers. In: Azar, Y., Bast, H., Herman, G. (eds.), 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 9:1\u20139:12, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"issue":"1","key":"23_CR10","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/jgt.20291","volume":"58","author":"E Chiniforooshan","year":"2008","unstructured":"Chiniforooshan, E.: A better bound for the cop number of general graphs. J. Graph Theory 58(1), 45\u201348 (2008)","journal-title":"J. Graph Theory"},{"key":"23_CR11","unstructured":"Clarke, N.E.B.: Constrained cops and robber. ProQuest LLC, Ann Arbor, MI, 2002. Thesis (Ph.D.)-Dalhousie University (Canada) (2002)"},{"key":"23_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Enright, J., Meeks, K., Pettersson, W., Sylvester, J.: Cops and robbers on multi-layer graphs. arXiv:2303.03962 (2023)","DOI":"10.1007\/978-3-031-43380-1_23"},{"key":"23_CR14","unstructured":"Fitzpatrick, S.L.: Aspects of domination and dynamic domination. ProQuest LLC, Ann Arbor, MI, 1997. Thesis (Ph.D.)-Dalhousie University (Canada) (1997)"},{"issue":"3","key":"23_CR15","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0166-218X(87)90033-3","volume":"17","author":"P Frankl","year":"1987","unstructured":"Frankl, P.: Cops and robbers in graphs with large girth and Cayley graphs. Discret. Appl. Math. 17(3), 301\u2013305 (1987)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"23_CR16","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1002\/jgt.20591","volume":"69","author":"AM Frieze","year":"2012","unstructured":"Frieze, A.M., Krivelevich, M., Loh, P.-S.: Variations on cops and robbers. J. Graph Theory 69(4), 383\u2013402 (2012)","journal-title":"J. Graph Theory"},{"key":"23_CR17","unstructured":"Joret, G., Kaminski, M., Theis, D.O.: The cops and robber game on graphs with forbidden (induced) subgraphs. Contrib. Discret. Math. 5(2) (2010)"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Kinnersley, W.B.: Cops and robbers is exptime-complete. J. Comb. Theory Ser. B 111, 201\u2013220 (2015)","DOI":"10.1016\/j.jctb.2014.11.002"},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"Lehner, F.: On the cop number of toroidal graphs. J. Comb. Theory, Ser. B 151, 250\u2013262 (2021)","DOI":"10.1016\/j.jctb.2021.06.008"},{"issue":"2","key":"23_CR20","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1002\/jgt.20642","volume":"71","author":"L Linyuan","year":"2012","unstructured":"Linyuan, L., Peng, X.: On Meyniel\u2019s conjecture of the cop number. J. Graph Theory 71(2), 192\u2013205 (2012)","journal-title":"J. Graph Theory"},{"issue":"4","key":"23_CR21","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1002\/rsa.20338","volume":"37","author":"T Luczak","year":"2010","unstructured":"Luczak, T., Pralat, P.: Chasing robbers on random graphs: zigzag theorem. Random Struct. Algorithms 37(4), 516\u2013524 (2010)","journal-title":"Random Struct. Algorithms"},{"issue":"2\u20133","key":"23_CR22","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0012-365X(83)90160-7","volume":"43","author":"RJ Nowakowski","year":"1983","unstructured":"Nowakowski, R.J., Winkler, P.: Vertex-to-vertex pursuit in a graph. Discret. Math. 43(2\u20133), 235\u2013239 (1983)","journal-title":"Discret. Math."},{"key":"23_CR23","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.dam.2022.05.019","volume":"320","author":"J Petr","year":"2022","unstructured":"Petr, J., Portier, J., Versteegen, L.: A faster algorithm for cops and robbers. Discret. Appl. Math. 320, 11\u201314 (2022)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"23_CR24","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1002\/rsa.20587","volume":"48","author":"P Pralat","year":"2016","unstructured":"Pralat, P., Wormald, N.C.: Meyniel\u2019s conjecture holds for random graphs. Random Struct. Algorithms 48(2), 396\u2013421 (2016)","journal-title":"Random Struct. Algorithms"},{"key":"23_CR25","unstructured":"Quilliot, A.: Jeux et pointes fixes sur les graphes. PhD thesis, Ph. D. Dissertation, Universit\u00e9 de Paris VI (1978)"},{"key":"23_CR26","doi-asserted-by":"crossref","unstructured":"Quilliot, A.: A short note about pursuit games played on a graph with a given genus. J. Comb. Theory Ser. B 38(1), 89\u201392 (1985)","DOI":"10.1016\/0095-8956(85)90093-0"},{"key":"23_CR27","doi-asserted-by":"crossref","unstructured":"Schroeder, B.S.W.: The copnumber of a graph is bounded by $$\\lfloor \\frac{3}{2}$$ genus $$(G)\\rfloor +3$$. In: Categorical perspectives (Kent, OH, 1998), Trends Math., pp. 243\u2013263. Birkh\u00e4user Boston, Boston, MA (2001)","DOI":"10.1007\/978-1-4612-1370-3_14"},{"issue":"3","key":"23_CR28","doi-asserted-by":"publisher","first-page":"1438","DOI":"10.1137\/100812963","volume":"25","author":"A Scott","year":"2011","unstructured":"Scott, A., Sudakov, B.: A bound for the cops and robbers problem. SIAM J. Discret. Math. 25(3), 1438\u20131442 (2011)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"23_CR29","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"PD Seymour","year":"1993","unstructured":"Seymour, P.D., Thomas, R.: Graph searching and a min-max theorem for tree-width. J. Comb. Theory Ser. B 58(1), 22\u201333 (1993)","journal-title":"J. Comb. Theory Ser. B"},{"key":"23_CR30","unstructured":"Sipser, M.: Introduction to the Theory of Computation. Cengage Learning, Boston (2012)"},{"key":"23_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-74642-5","volume-title":"The Mathematical Coloring Book","author":"A Soifer","year":"2009","unstructured":"Soifer, A.: The Mathematical Coloring Book. Springer, New York (2009). https:\/\/doi.org\/10.1007\/978-0-387-74642-5"},{"key":"23_CR32","doi-asserted-by":"crossref","unstructured":"Toru\u0144czyk, S.: Flip-width: cops and robber on dense graphs. In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS 2023), page to appear. IEEE (2023)","DOI":"10.1109\/FOCS57990.2023.00045"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43380-1_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T20:12:20Z","timestamp":1730146340000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43380-1_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031433795","9783031433801"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43380-1_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"23 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Fribourg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Switzerland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"49","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.unifr.ch\/wg2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}