In this talk, we consider the pursuit-evasion game Cops and Robbers. The game is played on a graph between two players: a set of cops and a single robber, who take turns moving along the edges. The cop number of a graph is the minimum number of cops needed to guarantee capture of the robber, meaning they eventually occupy the same vertex. This parameter has been studied on a wide range of graph classes. <\/p>\n
The underlying graph structure plays an important role in the cop number. We consider classes of graphs defined by forbidden substructures such as minors or induced subgraphs. A graph The role of forbidden minors in pursuit-evasion began in Andrae\u2019s work in 1986. For graphs that exclude a fixed minor In this talk, we consider the pursuit-evasion game Cops and Robbers. The game is played on a graph between two players: a set of cops and a single robber, who take turns moving along the edges. The cop number of a graph is the minimum number of cops needed to guarantee capture of the robber, meaning they eventually occupy the same vertex. This parameter has been studied on a wide range of graph classes. <\/p>\n","protected":false},"author":2,"featured_media":0,"template":"","meta":{"_uag_custom_page_level_css":"","site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"set","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_tribe_events_status":"","_tribe_events_status_reason":"","footnotes":""},"tags":[],"tribe_events_cat":[5],"class_list":["post-462","tribe_events","type-tribe_events","status-publish","hentry","tribe_events_cat-plenary-talk","cat_plenary-talk"],"spectra_custom_meta":{"_EventOrigin":["events-calendar"],"_tribe_modified_fields":["a:31:{s:12:\"_EventOrigin\";i:1777905020;s:10:\"_edit_last\";i:1777905042;s:10:\"post_title\";i:1777905053;s:11:\"post_status\";i:1777905155;s:12:\"post_content\";i:1777905155;s:16:\"tribe_events_cat\";i:1777905155;s:19:\"site-sidebar-layout\";i:1777905155;s:26:\"astra-migrate-meta-layouts\";i:1777916523;s:23:\"ast-site-content-layout\";i:1777905155;s:18:\"site-content-style\";i:1777905155;s:18:\"site-sidebar-style\";i:1777905155;s:29:\"theme-transparent-header-meta\";i:1777905155;s:17:\"_EventShowMapLink\";i:1777916523;s:13:\"_EventShowMap\";i:1777916523;s:13:\"_EventVenueID\";i:1777905155;s:17:\"_EventOrganizerID\";i:1777905155;s:15:\"_EventStartDate\";i:1777905155;s:13:\"_EventEndDate\";i:1777905155;s:18:\"_EventStartDateUTC\";i:1777905155;s:16:\"_EventEndDateUTC\";i:1777905155;s:14:\"_EventDuration\";i:1777905155;s:20:\"_EventCurrencySymbol\";i:1777905155;s:18:\"_EventCurrencyCode\";i:1777905155;s:22:\"_EventCurrencyPosition\";i:1777905155;s:10:\"_EventCost\";i:1777905155;s:9:\"_EventURL\";i:1777905155;s:14:\"_EventTimezone\";i:1777905155;s:18:\"_EventTimezoneAbbr\";i:1777905155;s:16:\"_uag_page_assets\";i:1783690066;s:18:\"_uag_css_file_name\";i:1777916939;s:12:\"post_excerpt\";i:1777916523;}"],"_edit_lock":["1777916830:2"],"_edit_last":["2"],"site-sidebar-layout":["default"],"ast-site-content-layout":["default"],"site-content-style":["default"],"site-sidebar-style":["default"],"theme-transparent-header-meta":["default"],"_EventShowMapLink":["1"],"_EventShowMap":["1"],"_EventVenueID":["337"],"_EventOrganizerID":["394"],"_EventStartDate":["2026-05-10 14:00:00"],"_EventEndDate":["2026-05-10 15:00:00"],"_EventStartDateUTC":["2026-05-10 14:00:00"],"_EventEndDateUTC":["2026-05-10 15:00:00"],"_EventDuration":["3600"],"_EventCurrencySymbol":["$"],"_EventCurrencyCode":["USD"],"_EventCurrencyPosition":["prefix"],"_EventCost":[""],"_EventURL":[""],"_EventTimezone":["UTC+0"],"_EventTimezoneAbbr":["UTC+0"],"astra-migrate-meta-layouts":["set"],"_uag_css_file_name":["uag-css-462.css"],"_uag_page_assets":["a:9:{s:3:\"css\";s:260:\".uag-blocks-common-selector{z-index:var(--z-index-desktop) !important}@media(max-width: 976px){.uag-blocks-common-selector{z-index:var(--z-index-tablet) !important}}@media(max-width: 767px){.uag-blocks-common-selector{z-index:var(--z-index-mobile) !important}}\";s:2:\"js\";s:0:\"\";s:18:\"current_block_list\";a:9:{i:0;s:11:\"core\/search\";i:1;s:10:\"core\/group\";i:2;s:12:\"core\/heading\";i:3;s:17:\"core\/latest-posts\";i:4;s:20:\"core\/latest-comments\";i:5;s:13:\"core\/archives\";i:6;s:15:\"core\/categories\";i:7;s:10:\"core\/image\";i:8;s:11:\"core\/spacer\";}s:8:\"uag_flag\";b:0;s:11:\"uag_version\";s:10:\"1783532082\";s:6:\"gfonts\";a:0:{}s:10:\"gfonts_url\";s:0:\"\";s:12:\"gfonts_files\";a:0:{}s:14:\"uag_faq_layout\";b:0;}"]},"uagb_featured_image_src":{"full":false,"thumbnail":false,"medium":false,"medium_large":false,"large":false,"1536x1536":false,"2048x2048":false},"uagb_author_info":{"display_name":"sjw3","author_link":"https:\/\/sites.cs.queensu.ca\/ocw2026\/author\/sjw3\/"},"uagb_comment_info":0,"uagb_excerpt":"In this talk, we consider the pursuit-evasion game Cops and Robbers. The game is played on a graph between two players: a set of cops and a single robber, who take turns moving along the edges. The cop number of a graph is the minimum number of cops needed to guarantee capture of the robber,…","_links":{"self":[{"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/tribe_events\/462","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/tribe_events"}],"about":[{"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/types\/tribe_events"}],"author":[{"embeddable":true,"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/users\/2"}],"version-history":[{"count":6,"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/tribe_events\/462\/revisions"}],"predecessor-version":[{"id":476,"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/tribe_events\/462\/revisions\/476"}],"wp:attachment":[{"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/media?parent=462"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/tags?post=462"},{"taxonomy":"tribe_events_cat","embeddable":true,"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/tribe_events_cat?post=462"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}G<\/code> is H<\/code>-free or H<\/code>-minor free if G<\/code> does not contain, respectively, any induced subgraph or minor which is isomorphic to H<\/code>.<\/p>\nH<\/code>, the upper bound for the cop-number is nearly the number of edges in this forbidden minor. More recently Chudnovsky et al. showed that excluding an induced subgraph of P5<\/sub><\/code> yields graphs that have cop number at most 2<\/code>. This talk presents two new results on both forbidden structure types. For graphs with forbidden minors, we present the necessary decomposition of the minor to bound the cop number. For graphs with path-like constraints, we present a significant improvement on the bound of the cop number.<\/p>\n","protected":false},"excerpt":{"rendered":"