{"id":374,"date":"2026-05-01T20:02:47","date_gmt":"2026-05-01T20:02:47","guid":{"rendered":"https:\/\/sites.cs.queensu.ca\/ocw2026\/?post_type=tribe_events&#038;p=374"},"modified":"2026-05-04T18:47:45","modified_gmt":"2026-05-04T18:47:45","slug":"large-degenerate-subgraphs-in-degenerate-graphs","status":"publish","type":"tribe_events","link":"https:\/\/sites.cs.queensu.ca\/ocw2026\/event\/large-degenerate-subgraphs-in-degenerate-graphs\/","title":{"rendered":"Large Degenerate Subgraphs in Degenerate Graphs"},"content":{"rendered":"<p><strong>Alexander Clow, Simon Fraser University<\/strong><\/p>\n<p>Given a graph G and a non-negative integer d let \u03b1d(G) be the order of a largest induced d-degenerate subgraph of G. We prove that for any pair of non-negative integers k &gt; d, if G is a k-degenerate graph, then \u03b1d(G) \u2265 max{(d+1)n\/k+d+1 , n \u2212 \u03b1k\u2212d\u22121(G)}.<\/p>\n<p>For k-degenerate graphs this improves a more general lower bound of Alon, Kahn, and Seymour. By modifying our arguments we also obtain an improved lower bounds on \u03b1d(G) for graphs of bounded genus. We will conclude by considering the open problem of determining \u03b1d(k) := infG with degeneracy k \u03b1d(G)\/|V (G)|.<\/p>\n<p>This is joint work with Sean Kim, and Ladislav Stacho.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Alexander Clow, Simon Fraser University Given a graph G and a non-negative integer d let \u03b1d(G) be the order of a largest induced d-degenerate subgraph of G. We prove that [&hellip;]<\/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":[4],"class_list":["post-374","tribe_events","type-tribe_events","status-publish","hentry","tribe_events_cat-contributed-talk","cat_contributed-talk"],"spectra_custom_meta":{"_EventOrigin":["events-calendar"],"_tribe_modified_fields":["a:30:{s:12:\"_EventOrigin\";i:1777665643;s:10:\"_edit_last\";i:1777665682;s:10:\"post_title\";i:1777665840;s:11:\"post_status\";i:1777665767;s:16:\"tribe_events_cat\";i:1777665767;s:19:\"site-sidebar-layout\";i:1777665767;s:26:\"astra-migrate-meta-layouts\";i:1777920465;s:23:\"ast-site-content-layout\";i:1777665767;s:18:\"site-content-style\";i:1777665767;s:18:\"site-sidebar-style\";i:1777665767;s:29:\"theme-transparent-header-meta\";i:1777665767;s:17:\"_EventShowMapLink\";i:1777920465;s:13:\"_EventShowMap\";i:1777920465;s:13:\"_EventVenueID\";i:1777665767;s:15:\"_EventStartDate\";i:1777665767;s:13:\"_EventEndDate\";i:1777665767;s:18:\"_EventStartDateUTC\";i:1777665767;s:16:\"_EventEndDateUTC\";i:1777665767;s:14:\"_EventDuration\";i:1777665767;s:20:\"_EventCurrencySymbol\";i:1777665767;s:18:\"_EventCurrencyCode\";i:1777665767;s:22:\"_EventCurrencyPosition\";i:1777665767;s:10:\"_EventCost\";i:1777665767;s:9:\"_EventURL\";i:1777665767;s:14:\"_EventTimezone\";i:1777665767;s:18:\"_EventTimezoneAbbr\";i:1777665767;s:16:\"_uag_page_assets\";i:1788601330;s:18:\"_uag_css_file_name\";i:1777920467;s:12:\"post_content\";i:1777920465;s:12:\"_wp_old_slug\";i:1777920428;}"],"_edit_lock":["1777920323: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"],"_EventStartDate":["2026-05-09 11:00:00"],"_EventEndDate":["2026-05-09 11:30:00"],"_EventStartDateUTC":["2026-05-09 11:00:00"],"_EventEndDateUTC":["2026-05-09 11:30:00"],"_EventDuration":["1800"],"_EventCurrencySymbol":["$"],"_EventCurrencyCode":["USD"],"_EventCurrencyPosition":["prefix"],"_EventCost":[""],"_EventURL":[""],"_EventTimezone":["UTC+0"],"_EventTimezoneAbbr":["UTC+0"],"_wp_old_slug":["alexander-clow-large-degenerate-subgraphs-in-degenerate-graphs"],"astra-migrate-meta-layouts":["set"],"_uag_css_file_name":["uag-css-374.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:\"1787951996\";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":"Alexander Clow, Simon Fraser University Given a graph G and a non-negative integer d let \u03b1d(G) be the order of a largest induced d-degenerate subgraph of G. We prove that [&hellip;]","_links":{"self":[{"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/tribe_events\/374","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":5,"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/tribe_events\/374\/revisions"}],"predecessor-version":[{"id":544,"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/tribe_events\/374\/revisions\/544"}],"wp:attachment":[{"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/media?parent=374"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/tags?post=374"},{"taxonomy":"tribe_events_cat","embeddable":true,"href":"https:\/\/sites.cs.queensu.ca\/ocw2026\/wp-json\/wp\/v2\/tribe_events_cat?post=374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}