<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 3" %>
A Note on Extendability and Factor-Criticality
Qinglin Yu
Department of Mathematics and Statistics, University College of The Cariboo, Kamloops, B.C. Canada
Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, P.R. China
Annals of Combinatorics 6 (3) p.479-481 September, 2002
AMS Subject Classification: 05C70
Let n be a non-negative integer. A graph G is said to be n- factor-critical if the subgraph G - S has a perfect matching for any subset S of V(G) with |S| = n. In this paper, we provide much shorter proofs of two main theorems about extendability and factor-criticality obtained by Favaron [2]. Furthermore, we present a solution to an open problem posted in the same paper.
Keywords: matching, k-extendable graphs, n-factor-critical graphs


1. O. Favaron, On k-factor-critical graphs, Discuss. Math. Graph Theory 16 (1996) 41每51.

2. O. Favaron, Extendability and factor-criticality, Discrete Math. 213 (2000) 115每122.

3. O. Favaron and M. Shi, Minimally k-factor-critical graphs, Australas. J. Combin. 17 (1998) 89每97.

4. G. Liu and Q. Yu, On n-edge-deletable and n-critical graphs, Bull. Inst. Combin. Appl. 24 (1998) 65每72.

5. L. Lov∩asz and M.D. Plummer, Matching Theory, North-Holland, Amsterdam, 1986.

6. M.D. Plummer, On n-extendable graphs, Discrete Math. 31 (1988) 201每210.

7. M.D. Plummer, Extending matchings in graphs: a survey, Discrete Math. 127 (1994) 277每 292.

8. Q. Yu, Characterizations of various matchings in graphs, Australas. J. Combin. 7 (1993) 55每64.

9. Q. Yu, A note on n-extendable graphs, J. Graph Theory 16 (1992) 349每353.