Partitions of graphs into small and large sets

Abstract

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$, $°(v)\le n-|A|+k$. A subset $B\subseteq V(G)$ is called \emph{$k$-large} if, for every vertex $u\in B$, $°(u)\ge |B|-k-1$. Moreover, we denote by ${\phi }_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 ${\phi }_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án Theorem and the Hansen-Zheng Theorem among other things.

21 pages

Cited by in corpus (1)

• New approach to the $k$-independence number of a graph