Minimum Degree, Independence Number and $(a,b,k)$-Critical Graphs

Abstract

Let $G$ be a graph, and let $a,b$, and $k$ be nonnegative integers with $0\le a\le b$. A graph $G$ is called an $(a,b,k)$-critical graph if after deleting any $k$ vertices of $G$, the remaining graph of $G$ has an $[a,b]$-factor. In this paper, we prove that if $\delta (G)\ge a+k$ and $\alpha (G)\le \frac{4b(\delta (G)-a+1-1)}{(a+1{)}^2}$, then $G$ is an $(a,b,k)$-critical graph. Furthermore, it is shown that the result in this paper is best possible in some sense.