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

Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, P.R. China

yu@cariboo.bc.ca

Annals of Combinatorics 6 (3) p.479-481 September, 2002

Abstract:

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.

References:

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.