A Note on Large Degenerate Induced Subgraphs in Sparse Graphs
The Electronic Journal of Combinatorics · 22.05.2026 · 33 (2)
DOI: 10.37236/14959 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 22.05.2026. Verfasst von Alexander Clow und 2 weiteren Autor:innen.
Abstract (Originalsprache)
Given a graph $G$ and a non-negative integer $d$ let $\alpha_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 $\alpha_d(G) \geq \max\{ \frac{(d+1)n}{k+d+1}, n - \alpha_{k-d-1}(G)\}$. 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 $\alpha_d(G)$ for graphs of bounded genus. This extends earlier work on degenerate subgraphs of planar graphs.
Zitieren
APA
Clow, A., Kim, S., & Stacho, L. (2026). A Note on Large Degenerate Induced Subgraphs in Sparse Graphs. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/14959
Vancouver
Clow A, Kim S, Stacho L. A Note on Large Degenerate Induced Subgraphs in Sparse Graphs. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/14959
BibTeX
@article{Clow2026,
author = {Clow, Alexander and Kim, Sean and Stacho, Ladislav},
title = {A Note on Large Degenerate Induced Subgraphs in Sparse Graphs},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {2},
doi = {10.37236/14959}
}
EUVIMED