{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:45:57Z","timestamp":1787319957085,"version":"build-2736575974"},"reference-count":10,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>In this note, we prove that for every integer $k$, there exist constants $g_{1}(k)$ and $g_{2}(k)$ such that the following holds. If $G$ is a graph on $n$ vertices with maximum degree $\\Delta$ then it contains an induced subgraph $H$ on at least $n - g_{1}(k)\\sqrt{\\Delta}$ vertices, such that $H$ contains $k$ vertices of the same degree of order at least $\\Delta(H)-g_{2}(k)$. This solves an approximate version of a conjecture of Caro and Yuster which states that $g_2(k)$ can be taken to be $0$ for every $k$. Note that in our result we allow the common degree to be at most an additive constant far from the maximum degree.<\/jats:p>","DOI":"10.1137\/17m1133907","type":"journal-article","created":{"date-parts":[[2018,2,6]],"date-time":"2018-02-06T13:00:43Z","timestamp":1517922043000},"page":"450-454","source":"Crossref","is-referenced-by-count":2,"title":["Large Induced Subgraphs with $k$ Vertices of Almost Maximum Degree"],"prefix":"10.1137","volume":"32","author":[{"given":"Ant\u00f3nio","family":"Gira\u0342o","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kamil","family":"Popielarz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,2,6]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90026-9"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/100785156"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"B. Bolloba\u0301s,\n                      Modern Graph Theory\n                      , Springer, New York, 1998.","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00355-Z"},{"key":"atypb5","unstructured":"Y. Caro, Y. Lauri, and C. Zarb,\n                      Equating Two Maximum Degrees\n                      , preprint, arXiv:1704.08472, 2017."},{"key":"atypb6","first-page":"16","author":"Caro Y.","year":"2013","journal-title":"Electronic Journal of Combinatorics"},{"key":"atypb7","doi-asserted-by":"crossref","first-page":"R7","DOI":"10.37236\/96","volume":"16","author":"Caro Y.","year":"2009","journal-title":"Electron. J. Combin."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2009.09.003"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000663"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1993.1023"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1133907","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:54:00Z","timestamp":1787316840000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1133907"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":10,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1133907"],"URL":"https:\/\/doi.org\/10.1137\/17m1133907","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}