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 \leq a \leq 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) \geq a + k\) and \(\alpha(G) \leq \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.