${\delta }_k$-small sets in graphs

Abstract

Let $G$ be a simple $n$-vertex graph and $W\subseteq\V(G)$. We say that $W$ is a ${\delta }_k$-small set if $$ \sqrt[k]{\frac{\sum_{v\in W}d^k(v)}{\abs W}}\leq n-\abs W. $$ Let ${\phi }^{(k)}(G)$ denote the smallest natural number $r$ such that $\V(G)$ decomposes into $r$ ${\delta }_k$-small sets, and let ${\alpha }^{(k)}(G)$ denote the maximal number of vertices in a ${\delta }_k$-small set of $G$. In this paper we obtain bounds for ${\alpha }^{(k)}(G)$ and ${\phi }^{(k)}(G)$. Since ${\phi }^{(k)}(G)\le \omega (G)\le \chi (G)$ and $\alpha (G)\le {\alpha }^{(k)}(G)$, we obtain also bounds for the clique number $\omega (G)$, the chromatic number $\chi (G)$ and the independence number $\alpha (G)$.