Equivalence between Extendibility and Factor-Criticality

Abstract

In this paper, we show that if \(k \geq \frac{v+2}{4}\), where \(v\) denotes the order of a graph, a non-bipartite graph \(G\) is \(k\)-extendable if and only if it is \(2k\)-factor-critical. If \(k \geq \frac{v-3}{4}\), a graph \(G\) is \(k\)-extendable if and only if it is \((2k+1)\)-factor-critical. We also give examples to show that the two bounds are best possible. Our results are answers to a problem posted by Favaron \([3]\) and Yu \([11]\).