ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 24(3) (2004) 431-441
DOI: 10.7151/dmgt.1242


Mekkia Kouider

Laboratoire de Recherche en Informatique
UMR 8623 Bât. 490, Université Paris Sud
91405 Orsay, France


Preben Dahl Vestergaard

Department of Mathematics
Aalborg University, Fredrik Bajers Vej 7G
DK-9220 Aalborg Øst, Denmark



Let a and b be integers 4 ≤ a ≤ b. We give simple, sufficient conditions for graphs to contain an even [a,b]-factor. The conditions are on the order and on the minimum degree, or on the edge-connectivity of the graph.

Keywords: even factor, eulerian, spanning subgraph.

2000 Mathematics Subject Classification: 05C70.


[1] J. Akiyama and M. Kano, Factors and factorizations of graphs - a survey, J. Graph Theory 9 (1985) 1-42, doi: 10.1002/jgt.3190090103.
[2] A. Amahashi, On factors with all degrees odd, Graphs and Combin. 1 (1985) 111-114, doi: 10.1007/BF02582935.
[3] Mao-Cheng Cai, On some factor theorems of graphs, Discrete Math. 98 (1991) 223-229, doi: 10.1016/0012-365X(91)90378-F.
[4] G. Chartrand and O.R. Oellermann, Applied and Algorithmic Graph Theory (McGraw-Hill, Inc., 1993).
[5] Y. Cui and M. Kano, Some results on odd factors of graphs, J. Graph Theory 12 (1988) 327-333, doi: 10.1002/jgt.3190120305.
[6] M. Kano, [a,b]-factorization of a graph, J. Graph Theory 9 (1985) 129-146, doi: 10.1002/jgt.3190090111.
[7] M. Kano and A. Saito, [a,b]-factors of a graph, Discrete Math. 47 (1983) 113-116, doi: 10.1016/0012-365X(83)90077-8.
[8] M. Kano, A sufficient condition for a graph to have [a,b]-factors, Graphs Combin. 6 (1990) 245-251, doi: 10.1007/BF01787576.
[9] M. Kouider and M. Maheo, Connected (a,b)-factors in graphs, 1998. Research report no. 1151, LRI, (Paris Sud, Centre d'Orsay). Accepted for publication in Combinatorica.
[10] M. Kouider and M. Maheo, 2 edge-connected [2,k]-factors in graphs, JCMCC 35 (2000) 75-89.
[11] M. Kouider and P.D. Vestergaard, On even [2,b]-factors in graphs, Australasian J. Combin. 27 (2003) 139-147.
[12] Y. Li and M. Cai, A degree condition for a graph to have [a,b]-factors, J. Graph Theory 27 (1998) 1-6, doi: 10.1002/(SICI)1097-0118(199801)27:1<1::AID-JGT1>3.0.CO;2-U.
[13] L. Lovász, Subgraphs with prescribed valencies, J. Comb. Theory 8 (1970) 391-416, doi: 10.1016/S0021-9800(70)80033-3.
[14] L. Lovász, The factorization of graphs II, Acta Math. Acad. Sci. Hungar. 23 (1972) 223-246, doi: 10.1007/BF01889919.
[15] J. Topp and P.D. Vestergaard, Odd factors of a graph, Graphs and Combin. 9 (1993) 371-381, doi: 10.1007/BF02988324.

Received 22 April 2003
Revised 9 October 2003