PreprintarXiv licencearXiv
Large induced subgraphs with k vertices of maximum degree
Abstract
We prove that, for every integer k≥ 2, there exists a constant ck>0 such that every graph on n≥ R(k,k) vertices with maximum degree Δ contains an induced subgraph on at least n−ck√Δ vertices whose maximum degree is attained by at least k vertices. This confirms a conjecture of Caro and Yuster in strong form.
Related
- On the Minimum Possible Maximum Degree of Induced Subgraphs of Product Graphs
- Small subgraphs of large minimum degree
- Unbalanced spectral Turán problem for color-critical graphs with prescribed large maximum degree
- Unbalanced Turán and spectral Turán problems with prescribed large maximum degree
- Decomposing multigraphs into two Class I subgraphs with prescribed maximum degrees
BibTeX
@misc{liu2026large,
title = {{Large induced subgraphs with $k$ vertices of maximum degree}},
author = {Zhen liu and Qinghou Zeng},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01681},
eprint = {2609.01681},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01681},
}
RIS
TY - UNPB
TI - Large induced subgraphs with k vertices of maximum degree
AU - Zhen liu
AU - Qinghou Zeng
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.01681
UR - https://arxiv.org/abs/2609.01681
AB - We prove that, for every integer k≥ 2, there exists a constant c_k>0 such that every graph on n≥ R(k,k) vertices with maximum degree Δ contains an induced subgraph on at least n−c_k√Δ vertices whose maximum degree is attained by at least k vertices. This confirms a conjecture of Caro and Yuster in strong form.
ER -