A graph of order $n$ is $p$-factor-critical, where $p$ is an integer of the same parity as $n$, if the removal of any set of $p$ vertices results in a graph with a perfect matching. 1-factor-critical graphs and 2-factor-critical graphs are well-known factor-critical graphs and bicritical graphs, respectively. It is known that if a connected vertex-transitive graph has odd order, then it is factor-critical, otherwise it is elementary bipartite or bicritical. In this paper, we show that a connected vertex-transitive non-bipartite graph of even order at least 6 is 4-factor-critical if and only if its degree is at least 5. This result implies that each connected non-bipartite Cayley graph of even order and degree at least 5 is 2-extendable.
@article{10_37236_4807,
author = {Wuyang Sun and Heping Zhang},
title = {4-factor-criticality of vertex-transitive graphs},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {3},
doi = {10.37236/4807},
zbl = {1339.05187},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4807/}
}
TY - JOUR
AU - Wuyang Sun
AU - Heping Zhang
TI - 4-factor-criticality of vertex-transitive graphs
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/4807/
DO - 10.37236/4807
ID - 10_37236_4807
ER -
%0 Journal Article
%A Wuyang Sun
%A Heping Zhang
%T 4-factor-criticality of vertex-transitive graphs
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/4807/
%R 10.37236/4807
%F 10_37236_4807
Wuyang Sun; Heping Zhang. 4-factor-criticality of vertex-transitive graphs. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/4807
