EUVIMEDObjevte EUVIMED
Crossref

A Note on Large Degenerate Induced Subgraphs in Sparse Graphs

Alexander Clow, Sean Kim, Ladislav Stacho

The Electronic Journal of Combinatorics · 2026-05-22 · 33 (2)

DOI: 10.37236/14959 ↗

At a glance

Journal article in The Electronic Journal of Combinatorics, published online on 2026-05-22. Written by Alexander Clow and 2 co-authors.

AbstraktBibliografické údajeCiteRelated studies

Abstract (original language)

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.

Cite

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}
}
Start for free →