EUVIMEDEUVIMED entdecken
Crossref

A Note on Large Degenerate Induced Subgraphs in Sparse Graphs

Alexander Clow, Sean Kim, Ladislav Stacho

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →