$δ_k$-small sets in graphs

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

No reviews yet.

No comments yet.