{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:45:18Z","timestamp":1759063518645,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Let $G = (V, E)$ be a graph and $k \\geq 0$ an integer. A $k$-independent set\u00a0$S \\subseteq G$ is a set of vertices such that the maximum degree in the graph induced by $S$ is at most $k$. Denote by $\\alpha_{k}(G)$ the maximum cardinality of a $k$-independent set of $G$. For a graph $G$ on $n$ vertices and average degree $d$, Tur\u00e1n's theorem asserts that $\\alpha_{0}(G) \\geq \\frac{n}{d+1}$, where the equality holds if and only if $G$ is a union of cliques of equal size. For general $k$ we prove that $\\alpha_{k}(G) \\geq \\dfrac{(k+1)n}{d+k+1}$, improving on the previous best bound $\\alpha_{k}(G) \\geq \\dfrac{(k+1)n}{ \\lceil d \\rceil+k+1}$ of\u00a0Caro and Hansberg [E-JC, 2013]. For $1$-independence we prove that equality holds if and only if $G$ is either an independent set or a union of almost-cliques of equal size (an almost-clique is a clique on an even number of vertices minus a $1$-factor). For $2$-independence, we prove that equality holds\u00a0if and only if $G$ is an independent set. Furthermore when $d&gt;0$ is an integer divisible by 3 we prove that $\\alpha_2(G) \\geq \\dfrac{3n}{d+3} \\left( 1 + \\dfrac{12}{5d^2 + 25d + 18} \\right)$.<\/jats:p>","DOI":"10.37236\/5730","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T10:55:47Z","timestamp":1578653747000},"source":"Crossref","is-referenced-by-count":3,"title":["New Results on $k$-Independence of Graphs"],"prefix":"10.37236","volume":"24","author":[{"given":"Shimon","family":"Kogan","sequence":"first","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2017,5,5]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v24i2p15\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v24i2p15\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T23:57:30Z","timestamp":1579219050000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v24i2p15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,5]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2017,4,13]]}},"URL":"https:\/\/doi.org\/10.37236\/5730","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2017,5,5]]},"article-number":"P2.15"}}