\((a,b,k)\)-critical graphs (Q1375824)

An \([a,b]\)-factor of a graph \(G\) is a spanning subgraph of \(G\) with each degree between \(a\) and \(b\). An \((a,b,k)\)-critical graph admits an \([a,b]\)-factor after the deletion of any \(k\) vertices. \((1,1,2)\)-critical graphs have been called \(2\)-critical graphs and studied by Lovász and Plummer. This paper focuses on \((a,b,k)\)-critical graphs when \(a < b\). This condition is known to simplify the existence problem of \([a,b]\)-factors [cf. \textit{K. Heinrich, P. Hell, D. G. Kirkpatrick} and \textit{G. Liu}, Discrete Math. 85, No. 3, 313-317 (1990; Zbl 0723.05101) and \textit{R. P. Anstee}, Discrete Appl. Math. 27, No. 1/2, 29-38 (1990; Zbl 0735.05060)]. The authors prove that in this case a graph \(G\) is \((a,b,k)\)-critical if and only if for any set \(S\) of at least \(k\) vertices \[ \sum_{j=0}^{a-1} (a-j)P_j(G-S) \leq b| S| - bk, \] where \(P_j(G-S)\) denotes the number of vertices of degree \(j\) in \(G-S\). As a consequence they derive a number of facts about \((a,b,k)\)-critical graphs---for instance they prove that any \([m,n]\)-graph with \(mb \geq na+bk\) is \((a,b,k)\)-critical. No proofs are given in this correspondence.