  Let $G$ be a graph on $n$ vertices. We call a subset $A$ of the vertex set
$V(G)$ \emph{$k$-small} if, for every vertex $v \in A$, $\deg(v) \le n - |A| +
k$. A subset $B \subseteq V(G)$ is called \emph{$k$-large} if, for every vertex
$u \in B$, $\deg(u) \ge |B| - k - 1$. Moreover, we denote by $\varphi_k(G)$ the
minimum integer $t$ such that there is a partition of $V(G)$ into $t$ $k$-small
sets, and by $\Omega_k(G)$ the minimum integer $t$ such that there is a
partition of $V(G)$ into $t$ $k$-large sets. In this paper, we will show tight
connections between $k$-small sets, respectively $k$-large sets, and the
$k$-independence number, the clique number and the chromatic number of a graph.
We shall develop greedy algorithms to compute in linear time both
$\varphi_k(G)$ and $\Omega_k(G)$ and prove various sharp inequalities
concerning these parameters, which we will use to obtain refinements of the
Caro-Wei Theorem, the Tur\'an Theorem and the Hansen-Zheng Theorem among other
things.
