Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.13693 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911273449422848 |
|---|---|
| author | Clow, Alexander Kim, Sean Stacho, Ladislav |
| author_facet | Clow, Alexander Kim, Sean Stacho, Ladislav |
| contents | Given a graph $G$ and a non-negative integer $d$ let $α_d(G)$ be the order of a largest induced $d$-degenerate subgraph of $G$. We prove that for any pair of non-negative integers $k>d$, if $G$ is a $k$-degenerate graph, then $α_d(G) \geq \max\{ \frac{(d+1)n}{k+d+1}, n - α_{k-d-1}(G)\}$. For $k$-degenerate graphs this improves a more general lower bound of Alon, Kahn, and Seymour. By modifying our argument we obtain improved lower bound on $α_d(G)$ for graphs of bounded genus. This extends earlier work on degenerate subgraphs of planar graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_13693 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Note on Large Degenerate Induced Subgraphs in Sparse Graphs Clow, Alexander Kim, Sean Stacho, Ladislav Combinatorics 05C69 Given a graph $G$ and a non-negative integer $d$ let $α_d(G)$ be the order of a largest induced $d$-degenerate subgraph of $G$. We prove that for any pair of non-negative integers $k>d$, if $G$ is a $k$-degenerate graph, then $α_d(G) \geq \max\{ \frac{(d+1)n}{k+d+1}, n - α_{k-d-1}(G)\}$. For $k$-degenerate graphs this improves a more general lower bound of Alon, Kahn, and Seymour. By modifying our argument we obtain improved lower bound on $α_d(G)$ for graphs of bounded genus. This extends earlier work on degenerate subgraphs of planar graphs. |
| title | A Note on Large Degenerate Induced Subgraphs in Sparse Graphs |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2511.13693 |