On the equivalence between Sachs extendability and Sachs criticality

Julian Allagan1, Kevin Pereyra2, Zan-Bo Zhang3
1Department of Mathematics, Computer Science, and Engineering Technology Elizabeth City State University, Elizabeth City, NC 27909, USA
2Departamento de Matematica, Universidad Nacional de San Luis, San Luis, Argentina
3School of Statistics and Data Science, Guangdong University of Finance and Economics, Guangzhou 510320

Abstract

The concept of k-extendability is a fundamental notion in matching theory and is closely related to factor-criticality. In a seminal work, Zhang et al. established sharp conditions under which these two concepts are equivalent. In this paper, we study the equivalence between extendability and factor-criticality from the perspective of Sachs subgraphs and discuss conditions under which these notions are equivalent.

Keywords: perfect matching, k-factor-critical graph, Sachs subgraphs, minimum degree