×

Graph factors and factorization: 1985–2003: a survey. (English) Zbl 1112.05088

Summary: In the most general sense, a factor of a graph \(G\) is just a spanning subgraph of \(G\) and a graph factorization of \(G\) is a partition of the edges of \(G\) into factors. However, as we shall see in the present paper, even this extremely general definition does not capture all the factor and factorization problems that have been studied in graph theory. Several previous survey papers have been written on this subject [F. Chung and R. Graham, Lond. Math. Soc., Lect. Note Ser. 52, 103–123 (1981; Zbl 0464.05046); J. Akiyama and M. Kano, J. Graph Theory 9, 1–42 (1985; Zbl 0587.05048); L. Volkmann, Jahresber. Dtsch. Math.-Ver. 97, 19–42 (1995; Zbl 0822.05053)] as well as an entire book on graph decompositions [J. Bosák, Decompositions of graphs (Kluwer Academic Publishers Group, Dordrecht etc.) (1990; Zbl 0701.05042)]. Our purpose here is to concentrate primarily on surveying the developments of the last 15–20 years in this exponentially growing field.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics

Keywords:

matching
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] S. Abbasi, Spanning subgraphs of dense graphs and a combinatorial problem on strings, Ph.D. Thesis, Rutgers The State University of New Jersey, 1998.
[2] Aharoni, R., A generalization of Tutte’s 1-factor theorem to countable graphs, J. combin. theory ser. B, 37, 199-209, (1984) · Zbl 0552.05044
[3] Aharoni, R., König’s duality theorem for infinite bipartite graphs, J. London math. soc., 29, 1-12, (1984) · Zbl 0505.05049
[4] Aharoni, R., Matchings in infinite graphs, J. combin. theory ser. B, 44, 87-125, (1988) · Zbl 0642.05048
[5] Aharoni, R., Infinite matching theory, Discrete math., 95, 5-22, (1991) · Zbl 0763.05074
[6] Aharoni, R.; Magidor, M.; Shore, R., On the strength of König’s duality theorem for infinite bipartite graphs, J. combin. theory ser. B, 54, 257-290, (1992) · Zbl 0754.05053
[7] Aharoni, R.; Nash-Williams, C., Marriage in infinite societies, (1984), Progress in Graph Theory Academic Press Toronto, pp. 71-79 · Zbl 0558.05049
[8] Aharoni, R.; Nash-Williams, C.; Shelah, S., A general criterion for the existence of transversals, Proc. London math. soc., 47, 43-68, (1983) · Zbl 0522.05002
[9] Akiyama, J.; Exoo, G.; Harary, F., Covering and packing in graphs III, cyclic and acyclic invariants, Math. slovaca, 30, 405-417, (1980) · Zbl 0458.05050
[10] Akiyama, J.; Exoo, G.; Harary, F., Covering and packing in graphs, IV. linear arboricity, Networks, 11, 69-72, (1981) · Zbl 0479.05027
[11] J. Akiyama, M. Kano, Path factors of a graph, Graphs and Applications, Boulder Colorada, 1982, Wiley, New York, 1984, pp. 1-21. · Zbl 0587.05048
[12] Akiyama, J.; Kano, M., Factors and factorizations of graphs—a survey, J. graph theory, 9, 1-42, (1985) · Zbl 0587.05048
[13] Akiyama, J.; Kano, M., Almost-regular factorization of graphs, J. graph theory, 9, 123-128, (1985) · Zbl 0617.05052
[14] Alon, N., The linear arboricity of graphs, Israel J. math., 62, 311-325, (1988) · Zbl 0673.05019
[15] Alon, H.; Caro, Y.; Yuster, R., Packing and covering dense graphs, J. combin. des., 6, 451-472, (1998) · Zbl 0914.05013
[16] Alon, N.; Friedland, S.; Kalai, G., Regular subgraphs of almost regular graphs, J. combin. theory ser. B, 37, 79-91, (1984) · Zbl 0527.05059
[17] Alon, N.; Friedland, S.; Kalai, G., Every 4-regular graph plus an edge contains a 3-regular subgraph, J. combin. theory ser. B, 37, 92-93, (1984) · Zbl 0546.05054
[18] Alon, N.; McDiarmid, C.; Reed, B., Star arboricity, Combinatorica, 12, 375-380, (1992) · Zbl 0780.05043
[19] Alon, N.; Teague, V.; Wormald, N., Linear arboricity and linear k-arboricity of regular graphs, Graphs combin., 17, 11-16, (2001) · Zbl 0982.05079
[20] Amahashi, A., On factors with all degrees odd, Graphs combin., 1, 111-114, (1985) · Zbl 0573.05044
[21] Amahashi, A.; Kano, M., On factors with given components, Discrete math., 42, 1-6, (1982) · Zbl 0525.05048
[22] Anderson, I., Sufficient conditions for matching, Proc. edinb. math. soc., 18, 129-136, (1972/73) · Zbl 0248.05130
[23] Ando, K.; Egawa, Y.; Kaneko, A.; Kawarabayashi, K.; Matsuda, H., Path factors in claw-free graphs, Discrete math., 243, 195-200, (2002) · Zbl 0992.05060
[24] Anstee, R., An algorithmic proof of Tutte’s \(f\)-factor theorem, J. algorithms, 6, 112-131, (1985) · Zbl 0562.05038
[25] Anstee, R., Simplified existence theorems for (\(g, f\))-factors, Discrete appl. math., 27, 29-38, (1990) · Zbl 0735.05060
[26] Anstee, R., Matching theory: fractional to integral, New Zealand J. math., 21, 17-32, (1992) · Zbl 0772.05076
[27] Anstee, R.; Nam, Y., More sufficient conditions for a graph to have factors, Discrete math., 184, 15-24, (1998) · Zbl 0958.05106
[28] Anstee, R.; Nam, Y., Convexity of degree sequences, J. graph theory, 30, 147-156, (1999) · Zbl 0915.05093
[29] Bäbler, F., Über die zerlegung regulärer streckencomplexe ungerader ordnung, Comment. math. helv., 10, 275-287, (1938) · JFM 64.0596.01
[30] E. Balas, Integer and fractional matchings, Studies on graphs and discrete programming (Brussels, 1979); Ann. Discrete Math. 11 (1981), North-Holland, Amsterdam, New York, pp. 1-13. · Zbl 0481.05055
[31] Beineke, L., Graph decompositions, Congress. numer., 115, 213-226, (1996) · Zbl 0901.05076
[32] Bermond, J.-C.; Las Vergnas, M., Regular factors in nearly regular graphs, Discrete math., 50, 9-13, (1984) · Zbl 0543.05051
[33] Bertram, E.; Horák, P., Decomposing 4-regular graphs into triangle-free 2-factors, SIAM J. discrete math., 10, 309-317, (1997) · Zbl 0867.05054
[34] Biedl, T.; Bose, P.; Demaine, E.; Lubiw, A., Efficient algorithms for Petersen’s matching theorem, J. algorithms, 38, 110-134, (2001) · Zbl 0969.68179
[35] M. Blum, A new approach to maximum matchings in general graphs, languages and programming, Proceedings of the 17th International Colloquium on Automata, 1990, pp. 586-597. · Zbl 0765.68044
[36] Bollobás, B., Extremal graph theory, (1978), Academic Press London, New York, xx+488pp · Zbl 0419.05031
[37] Bollobás, B., Random graphs, (1985), Academic Press Inc., Harcourt Brace Jovanovich, Publishers London · Zbl 0567.05042
[38] Bollobás, B., Random graphs, (2001), Cambridge University Press Cambridge · Zbl 0997.05049
[39] Bollobás, B.; Cooper, C.; Fenner, T.; Frieze, A., Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least \(k\), J. graph theory, 34, 42-59, (2000) · Zbl 0958.05122
[40] Bollobás, B.; Fenner, T.; Frieze, A., Hamilton cycles in random graphs of minimal degree at least \(k\), A tribute to paul Erdős, (1990), Cambridge University Press Cambridge, pp. 59-95
[41] Bollobás, B.; McKay, B., The number of matchings in random regular graphs and bipartite graphs, J. combin. theory ser. B, 41, 80-91, (1996) · Zbl 0602.05050
[42] Bollobás, B.; Saito, A.; Wormald, N., Regular factors of regular graphs, J. graph theory, 9, 97-103, (1985) · Zbl 0612.05049
[43] Bosák, J., Disjoint factors of diameter two in complete graphs, J. combin. theory ser. B, 16, 57-63, (1974) · Zbl 0256.05117
[44] Bosák, J., Decompositions of graphs, (1990), Kluwer Academic Publishers Group Dordrecht · Zbl 0701.05042
[45] Bosák, J.; Rosa, A.; Znám, Š., On decompositions of complete graphs into factors with given diameters, (), 37-56
[46] Bourjolly, J.-M.; Pulleyblank, W., König-egerváry graphs, 2-bicritical graphs and fractional matchings, Discrete appl. math., 24, 63-82, (1989) · Zbl 0684.05036
[47] Brandt, S.; Chen, G.; Faudree, R.; Gould, R.J.; Lesniak, L., Degree conditions for 2-factors, J. graph theory, 24, 165-173, (1997) · Zbl 0879.05060
[48] Brègman, L.; Brègman, L., Certain properties of nonnegative matrices and their permanents, Dokl. akad. nauk SSSR, Soviet math. dokl., 14, 945-949, (1973), (English translation). · Zbl 0293.15010
[49] Brualdi, R., Strong transfinite versions of König’s duality theorem, Monatsh. math., 75, 106-110, (1971) · Zbl 0219.05070
[50] Bryś, K.; Lonc, Z., A complete solution of a holyer problem, ()
[51] Cariolaro, D.; Hilton, A., Class 1 graphs associated with regular graphs of high degree, Congr. numer., 159, 133-142, (2002) · Zbl 1024.05025
[52] Catlin, P., Subgraphs of graphs, I, Discrete math., 10, 225-233, (1974) · Zbl 0289.05122
[53] Cheah, F.; Corneil, D., The complexity of regular subgraph recognition, Discrete appl. math., 27, 59-68, (1990), Addendum: Discrete Appl. Math. 31 (1990) 309 · Zbl 0698.68040
[54] Chen, C., \(f\)-star factors with given properties, Acta math. sci. (Chinese), 11, 36-43, (1991)
[55] Chen, C.; Egawa, Y.; Kano, M., Star factors with given properties, Ars combin., 28, 65-70, (1989) · Zbl 0723.05099
[56] Chen, C.; Kano, M., Odd and even factors with given properties, Chinese quart. J. math., 7, 65-71, (1992) · Zbl 0964.05541
[57] Chen, G.; Faudree, J.; Gould, R.; Saito, A., 2-factors in claw-free graphs, Discuss. math. graph theory, 20, 165-172, (2000) · Zbl 0979.05067
[58] Chetwynd, A.; Hilton, A., Star multigraphs with three vertices of maximum degree, Math. proc. Cambridge philos. soc., 100, 303-317, (1986)
[59] Chetwynd, A.; Hilton, A., 1-factorizing regular graphs with high degree: an improved bound, Discrete math., 75, 103-112, (1989) · Zbl 0675.05030
[60] F. Chung, R. Graham, Recent results in graph decompositions, London Mathematical Society, Lecture Note Series, vol. 52, Cambridge University Press, 1981, pp. 103-123. · Zbl 0464.05046
[61] Chvátal, V., Tough graphs and Hamiltonian circuits, Discrete math., 5, 215-228, (1973) · Zbl 0256.05122
[62] Chvátal, V.; Fleischner, H.; Sheehan, J.; Thomassen, C., Three-regular subgraphs of four-regular graphs, J. graph theory, 3, 371-386, (1979) · Zbl 0427.05055
[63] Colbourn, C.; Rosa, A., Triple systems, (1999), The Clarendon Press, Oxford University Press New York · Zbl 0938.05009
[64] Cooper, C.; Frieze, A.; Molloy, M.; Reed, B., Perfect matchings in random \(r\)-regular, \(s\)-uniform hypergraphs, Combin. probab. comput., 5, 1-14, (1996) · Zbl 0857.05075
[65] Cornuéjols, G.; Hartvigsen, D., An extension of matching theory, J. combin. theory ser. B, 40, 285-296, (1986) · Zbl 0563.05048
[66] Cornuéjols, G.; Hartvigsen, D.; Pulleyblank, W., Packing subgraphs in a graph, Oper. res. lett., 1, 139-143, (1982) · Zbl 0488.90070
[67] Cornuéjols, G.; Pulleyblank, W., Perfect triangle-free 2-matchings, combinatorial optimization II (Proceedings of conference university of east anglia, Norwich, 1979), Math. program. stud., 13, 1-7, (1980)
[68] Cornuéjols, G.; Pulleyblank, W., Critical graphs, matchings and tours or a hierarchy of relaxations for the traveling salesman problem, Combinatorica, 3, 35-52, (1983) · Zbl 0535.05038
[69] Corrádi, K.; Hajnal, A., On the maximal number of independent circuits in a graph, Acta math. acad. sci. hungar., 14, 423-439, (1963) · Zbl 0118.19001
[70] Csiszár, I.; Körner, J., Graph decomposition: a new key to coding theorems, IEEE trans. inform. theory, 27, 5-12, (1981) · Zbl 0474.94022
[71] Cui, Y.; Kano, M., Some results on odd factors of graphs, J. graph theory, 12, 327-333, (1988) · Zbl 0661.05049
[72] Diestel, R., Graph decompositions. A study in infinite graph theory, (1990), The Clarendon Press, Oxford University Press New York · Zbl 0726.05001
[73] R. Diestel, Decomposing infinite graphs, Contemporary Methods in Graph Theory, Bibliographisches Inst., Mannheim, 1990, 261-289.
[74] Diestel, R., Decomposing infinite graphs, Discrete math., 95, 69-89, (1991) · Zbl 0759.05069
[75] Dor, D.; Tarsi, M., Graph decomposition is \(\mathit{NP}\)-complete: a complete proof of Holyer’s conjecture, SIAM J. comput., 26, 1166-1187, (1997) · Zbl 0884.05071
[76] Edmonds, J., Paths, trees and flowers, Canad. J. math., 17, 449-467, (1965) · Zbl 0132.20903
[77] Edmonds, J.; Johnson, E., Matching: a well solved class of integer linear programs, combinatorial structures and their applications, (1970), Gordon and Breach New York, pp. 89-92
[78] Egawa, Y., Era’s conjecture on \([k, k + 1]\)-factorizations of regular graphs, Ars combin., 21, 217-220, (1986) · Zbl 0647.05047
[79] Egawa, Y.; Enomoto, H., Sufficient conditions for the existence of \(k\)-factors, recent studies in graph theory, (1989), Vishwa Gulbarga, pp. 96-105
[80] Egawa, Y.; Enomoto, H.; Faudree, R.; Li, H.; Schiermeyer, I., Two-factors each component of which contains a specified vertex, J. graph theory, 43, 188-198, (2003) · Zbl 1024.05073
[81] Egawa, Y.; Enomoto, H.; Saito, A., Factors and induced subgraphs, Discrete math., 68, 179-189, (1988) · Zbl 0673.05070
[82] Egawa, Y.; Enomoto, H.; Tokushige, N., Graph decompositions through prescribed vertices without isolates, Ars combin., 62, 189-205, (2002) · Zbl 1072.05558
[83] Egawa, Y.; Faudree, R.; Györi, E.; Ishigami, Y.; Schelp, R.; Wang, H., Vertex-disjoint cycles containing specified edges, Graphs combin., 16, 81-92, (2000) · Zbl 0951.05061
[84] Egawa, Y.; Kano, M., Sufficient conditions for graphs to have \((g, f)\)-factors, Discrete math., 151, 87-90, (1996) · Zbl 0853.05061
[85] Egawa, Y.; Kano, M.; Kelmans, A.K., Star partitions of graphs, J. graph theory, 25, 185-190, (1997) · Zbl 0877.05045
[86] Egawa, Y.; Ota, K., Regular factors in \(K_{1, n}\)-free graphs, J. graph theory, 15, 337-344, (1991) · Zbl 0756.05088
[87] Egawa, Y.; Ota, K., Vertex-disjoint claws in graphs, Discrete math., 197/198, 225-246, (1999) · Zbl 0934.05077
[88] Y. Egawa, K. Ota, \(K_{1, 3}\)-factors in graphs, preprint, 2002.
[89] Egoryc‘ev, G., Solution of the Van der Waerden problem for permanents, Sibirsk. mat. zh., 22, 65-71, (1981), 225 (in Russian)
[90] Egoryc‘ev, G., The solution of Van der Waerden’s problem for permanents, Adv. math., 42, 299-305, (1981) · Zbl 0478.15003
[91] Ellingham, M., Isomorphic factorizations of regular graphs of even degree, J. austral. math. soc. ser. A, 44, 402-420, (1988) · Zbl 0673.05072
[92] Ellingham, M., Isomorphic factorization of \(r\)-regular graphs into \(r\) parts, Discrete math., 69, 19-34, (1988) · Zbl 0685.05032
[93] Ellingham, M.; Nam, Y.; Voss, H.-J., Connected \((g, f)\)-factors, J. graph theory, 39, 62-75, (2002) · Zbl 0995.05117
[94] Ellingham, M.; Wormald, N., Isomorphic factorization of regular graphs and 3-regular multigraphs, J. London math. soc., 37, 14-24, (1988) · Zbl 0685.05033
[95] El-Zahár, M., On circuits in graphs, Discrete math., 50, 227-230, (1984) · Zbl 0548.05037
[96] Enomoto, H., Graph decompositions without isolated vertices, J. combin. theory ser. B, 63, 111-124, (1995) · Zbl 0834.05046
[97] Enomoto, H.; Jackson, B.; Katerinis, P.; Saito, A., Toughness and the existence of \(k\)-factors, J. graph theory, 9, 87-95, (1985) · Zbl 0598.05054
[98] Enomoto, H.; Matsunaga, S., Graph decompositions without isolated vertices II, J. math. soc. Japan, 49, 161-180, (1997) · Zbl 0907.05041
[99] Enomoto, H.; Matsunaga, S., Graph decompositions without isolated vertices III, J. graph theory, 24, 155-164, (1997) · Zbl 0863.05066
[100] Enomoto, H.; Ota, K.; Kano, M., A sufficient condition for a bipartite graph to have a \(k\)-factor, J. graph theory, 12, 141-151, (1988) · Zbl 0718.05044
[101] Enomoto, H.; Tokuda, T., Complete-factors and \(f\)-factors, Discrete math., 220, 239-242, (2000) · Zbl 0955.05079
[102] Era, H., Semiregular factorizations of regular graphs, graphs and applications, Boulder, colorado, 1982, (1985), Wiley, pp. 101-116
[103] P. Erdős, A. Hajnal, On spanned subgraphs of graphs, Contributions to Graph Theory and its Applications, International Colloquium, Oberhof, 1977, Tech. Hochschule Ilmenau, 1977, pp. 80-96.
[104] Erdős, P.; Rényi, A., On the existence of a factor of degree one of a connected random graph, Acta math. acad. sci. hungar., 17, 359-368, (1966) · Zbl 0203.56902
[105] Falikman, D.; Falikman, D., Proof of the Van der Waerden conjecture on the permanent of a doubly stochastic matrix, Mat. zametki, Math. notes, 29, 475-479, (1981), 957 (in Russian) · Zbl 0475.15007
[106] Faudree, R.; Favaron, O.; Flandrin, E.; Li, H.; Liu, Z., On 2-factors in claw-free graphs, Discrete math., 206, 131-137, (1999) · Zbl 0981.05084
[107] Feng, C., Existence for \(k\)-factors in claw-free graphs, Xinan shifan daxue xuebao ziran kexue ban, 24, 276-279, (1999), (in Chinese)
[108] Fiorini, S., A bibliographic survey of edge-colourings, J. graph theory, 2, 93-106, (1978) · Zbl 0406.05032
[109] S. Fiorini, R. Wilson, Edge-colourings of graphs, Research Notes in Mathematics, vol. 16, Pitman, London, 1977. · Zbl 0421.05023
[110] C. Fremuth-Paeger, Degree constrained subgraph problems and network flow optimization, Dissertation, Universität Augsburg, Augsburg, 1997, Augsburger Mathematisch-Naturwissenschaftliche Schriften, Augsburg Mathematical-Scientific Texts, vol. 21, Dr. Bernd Wissner, Augsburg, 1997. · Zbl 0884.05074
[111] Fremuth-Paeger, C.; Jungnickel, D., Balanced network flows, I. A unifying framework for design and analysis of matching algorithms, Networks, 33, 1-28, (1999) · Zbl 0999.90005
[112] Fremuth-Paeger, C.; Jungnickel, D., Balanced network flows, II. simple augmentation algorithms, Networks, 33, 29-41, (1999) · Zbl 0999.90006
[113] Fremuth-Paeger, C.; Jungnickel, D., Balanced network flows, III. strongly polynomial augmentation algorithms, Networks, 33, 43-56, (1999) · Zbl 0999.90007
[114] Fremuth-Paeger, C.; Jungnickel, D., Balanced network flows, IV. duality and structure theory, Networks, 37, 194-201, (2001) · Zbl 1038.90007
[115] Frieze, A.; Janson, S., Perfect matchings in random \(s\)-uniform hypergraphs, Random structures algorithms, 7, 41-57, (1995) · Zbl 0839.05074
[116] Frobenius, G., Über matrizen aus nicht negativen elementen, Sitzungsber. König. preuss. akad. wiss., 26, 456-477, (1912) · JFM 43.0204.09
[117] Fronček, D., Decompositions of complete bipartite and tripartite graphs into self-complementary factors with finite diameters, Graphs combin., 12, 305-320, (1996) · Zbl 0866.05050
[118] Fujita, S., Vertex-disjoint \(K_{1, t}\)’s in graphs, Ars combin., 64, 211-223, (2002) · Zbl 1074.05506
[119] Fulkerson, D.; Hoffman, A.; McAndrew, M., Some properties of graphs with multiple edges, Canad. J. math., 17, 166-177, (1965) · Zbl 0132.21002
[120] Gabow, H.; Kaplan, H.; Tarjan, R., Unique maximum matching algorithms, annual ACM symposium on theory of computing, Atlanta, GA, 1999 (electronic), (1999), ACM New York, pp. 70-78
[121] Gabow, H.; Kaplan, H.; Tarjan, R., Unique maximum matching algorithms, J. algorithms, 40, 159-183, (2001) · Zbl 0982.05094
[122] Gabow, H.; Tarjan, R., Faster scaling algorithms for general graph-matching problems, J. assoc. comput. Mach., 38, 815-853, (1991) · Zbl 0799.68145
[123] Gardiner, A., Embedding \(k\)-regular graphs in \(k + 1\)-regular graphs, J. London math. soc., 28, 393-400, (1983) · Zbl 0511.05040
[124] Garey, M.; Johnson, D., Computers and intractability, A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[125] Garey, M.; Johnson, D.; Tarjan, R., The planar Hamiltonian circuit problem is NP-complete, SIAM J. comput., 5, 704-714, (1976) · Zbl 0346.05110
[126] Gould, R., Updating the Hamiltonian problem—a survey, J. graph theory, 15, 121-157, (1991) · Zbl 0746.05039
[127] Gould, R., Advances on the Hamiltonian problem—a survey, Graphs combin., 19, 7-52, (2003) · Zbl 1024.05057
[128] Guldan, F., Some results on linear arboricity, J. graph theory, 10, 505-509, (1986) · Zbl 0651.05029
[129] Gunther, G.; Hartnell, B.; Rall, D., Star-factors and \(k\)-bounded total domination, Networks, 27, 197-201, (1996) · Zbl 0854.05088
[130] T. Gustavsson, Decompositions of large graphs and digraphs with high minimum degree, Ph.D. Dissertation, Department of Mathematics, University of Stockholm, 1991.
[131] E. Györi, On division of graphs to connected subgraphs, Combinatorics, Proceedings of the Fifth Hungarian Colloquium, Keszthely, 1976, vol. I, North-Holland, Amsterdam, New York, 1978, pp. 485-494.
[132] Habib, M.; Péroche, B., Some problems about linear arboricity, Discrete math., 41, 219-220, (1982) · Zbl 0486.05053
[133] Hajnal, P., Partition of graphs with condition on the connectivity and minimum degree, Combinatorica, 3, 95-99, (1983) · Zbl 0529.05030
[134] Hall, M., Distinct representatives of subsets, Bull. amer. math. soc., 54, 922-926, (1948) · Zbl 0032.27101
[135] Hall, P., On representatives of subsets, J. London math. soc., 10, 26-30, (1935) · Zbl 0010.34503
[136] Harary, F., Covering and packing graphs I, Ann. New York acad. sci., 175, 198-205, (1970) · Zbl 0226.05119
[137] Harary, F.; Robinson, R.; Wormald, N., Isomorphic factorisations, I. complete graphs, Trans. amer. math. soc., 242, 243-260, (1978) · Zbl 0381.05044
[138] Harary, F.; Wallis, W., Isomorphic factorizations, II. combinatorial designs, Congress. numer., XIX, 13-28, (1977) · Zbl 0405.05016
[139] D. Hartvigsen, Extensions of matching theory, Ph.D. Thesis, Carnegie-Mellon University, 1984.
[140] D. Hartvigsen, The square-free 2-factor problem in bipartite graphs, Integer Programming and Combinatorial Optimization, Seventh IPCO Conference, Graz, Austria, 1999, Lecture Notes in Computer Science, vol. 1610, Springer, Berlin, 1999, pp. 234-241. · Zbl 0948.90142
[141] Heinrich, K.; Hell, P.; Kirkpatrick, D.; Liu, G., Communication: a simple existence criterion for \((g < f)\)-factors, Discrete math., 85, 313-317, (1990) · Zbl 0723.05101
[142] P. Hell, Graph packings, Discrete Mathematics, Electronic Notes, 2000.
[143] Hell, P.; Kirkpatrick, D., On generalized matching problems, Inform. process. lett., 12, 33-35, (1981) · Zbl 0454.68077
[144] P. Hell, D. Kirkpatrick, Scheduling, matching and coloring, Algebraic Methods in Graph Theory, vols. I, II (Szeged, 1978), North-Holland, Amsterdam, New York, 1981, pp. 273-279.
[145] P. Hell, D. Kirkpatrick, Star factors and star packings, TR 82-6, Department of Computing Science, Simon Fraser University, 1982.
[146] Hell, P.; Kirkpatrick, D., Packings by complete bipartite graphs, SIAM J. algebraic discrete methods, 7, 199-209, (1986) · Zbl 0597.05050
[147] Hell, P.; Kirkpatrick, D.; Kratochvíl, J.; Kříž, I., On restricted two-factors, SIAM J. discrete math., 1, 472-484, (1988) · Zbl 0672.05065
[148] Hell, P.; Kirkpatrick, D.; Li, B., Rounding in symmetric matrices and undirected graphs, Discrete appl. math., 70, 1-21, (1996) · Zbl 0920.05062
[149] Hendry, G., Maximum graphs with a unique k-factor, J. combin. theory ser. B, 37, 53-63, (1984) · Zbl 0535.05036
[150] Híc, P.; Palumbíny, D., Isomorphic factorisations of complete graphs into factors with a given diameter, Math. slovaca, 37, 247-254, (1987) · Zbl 0675.05051
[151] Hilton, A., Canonical edge-colourings of locally finite graphs, Combinatorica, 2, 37-51, (1982) · Zbl 0494.05021
[152] Hilton, A., Factorizations of regular graphs of high degree, J. graph theory, 9, 193-196, (1985) · Zbl 0624.05050
[153] Hilton, A., Recent progress on edge-colouring graphs, Discrete math., 64, 303-307, (1987) · Zbl 0622.05021
[154] Hilton, A., Recent results on edge-colouring graphs, with applications to the total-chromatic number, J. combin. math. combin. comput., 3, 121-134, (1988) · Zbl 0661.05025
[155] A. Hilton, \((r, r + 1)\)-factorizations of \((d, d + 1)\)-graphs, submitted. · Zbl 1136.05058
[156] Hilton, A.; Holroyd, F.; Zhao, C., The overfull conjecture and the conformability conjecture, Discrete math., 241, 343-361, (2001) · Zbl 0992.05037
[157] Hilton, A.; Johnstone, W., Some problems about r-factorizations of complete graphs, J. combin. math. combin. comput., 35, 3-49, (2000) · Zbl 0967.05048
[158] A. Hilton, R. Wilson, Edge-colouring of graphs: a progress report, Graph Theory and its Applications: East and West (Jinan, 1986), Ann. New York Acad. Sci. 576, New York, 1989, pp. 241-249. · Zbl 0792.05052
[159] Hoffman, D.; Rodger, C., On the number of edge-disjoint one factors and the existence of k-factors in complete multipartite graphs, Discrete math., 160, 177-187, (1996) · Zbl 0860.05058
[160] A. Hoffmann, Regular factors in regular multipartite graphs, Sixth International Conference on Graph Theory (Marseille, 2000), 4pp (electronic), Electronic Notes in Discrete Mathematics, vol. 5, Elsevier, Amsterdam, 2000. · Zbl 1412.05162
[161] Hoffmann, A., Regular factors in regular multipartite graphs, Discrete math., 258, 43-62, (2002) · Zbl 1013.05061
[162] Hoffmann, A., Regular factors in connected regular graphs, Ars combin., 68, 235-242, (2003) · Zbl 1072.05046
[163] A. Hoffmann, L. Volkmann, Extremal bipartite graph with a unique k-factor, preprint, 2003.
[164] Hoffmann, A.; Volkmann, L., On unique k-factors and unique [1,k]-factors in graphs, Discrete math., 278, 127-138, (2004) · Zbl 1041.05060
[165] A. Hoffmann, L. Volkmann, On regular factors in regular graphs with small radius, Electron. J. Combin. 11, 2004; Research Paper 7, 7pp (electronic). · Zbl 1043.05098
[166] Holyer, I., The NP-completeness of edge-coloring, SIAM J. comput., 10, 718-720, (1981) · Zbl 0473.68034
[167] Holyer, I., The NP-completeness of some edge partition problems, SIAM J. comput., 10, 713-717, (1981) · Zbl 0468.68069
[168] M. Holz, K.-P. Podewski, K. Steffens, Injective Choice Functions, Lecture Notes in Mathematics, vol. 1238, Springer, Berlin, 1987. · Zbl 0608.05003
[169] Hrnčiar, P., On decompositions of complete graphs into three factors with given diameters, Czechoslovak math. J., 40, 115, 388-396, (1990) · Zbl 0748.05075
[170] Iida, T.; Nishimura, T., An ore-type condition for the existence of k-factors in graphs, Graphs combin., 7, 353-361, (1991) · Zbl 0763.05082
[171] Iida, T.; Nishimura, T., Neighborhood conditions and k-factors, Tokyo J. math., 20, 411-418, (1997) · Zbl 0897.05064
[172] Ishigami, Y.; Jiang, T., Vertex-disjoint cycles containing prescribed vertices, J. graph theory, 42, 276-296, (2003) · Zbl 1017.05058
[173] Jackson, B.; Whitty, R., A note concerning graphs with unique f-factors, J. graph theory, 13, 577-580, (1989) · Zbl 0692.05050
[174] Janson, S., The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph, Combin. probab. comput., 3, 97-126, (1994) · Zbl 0809.05084
[175] Janson, S.; Łuczak, T.; Ruciński, A., Random graphs, (2000), Wiley Interscience New York
[176] Jensen, T.; Toft, B., Graph coloring problems, (1995), Wiley-Interscience New York · Zbl 0855.05054
[177] Johann, P., On the structure of graphs with a unique \(k\)-factor, J. graph theory, 35, 227-243, (2000) · Zbl 0965.05080
[178] P. Johann, On the structure of graphs with a unique k-factor, Sixth International Conference on Graph Theory, Marseille, 2000, Electronic Notes in Discrete Mathematics, vol. 5, Elsevier, Amsterdam, 2000, 3pp (electronic).
[179] Johansson, R., On the bipartite case of el-zahár’s conjecture, Discrete math., 219, 123-134, (2000) · Zbl 0947.05046
[180] Kaneko, A., A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two, J. combin. theory ser. B, 88, 195-218, (2003) · Zbl 1029.05125
[181] Kaneko, A.; Kelmans, A.; Nishimura, T., On packing 3-vertex paths in a graph, J. graph theory, 36, 175-197, (2001) · Zbl 1060.05081
[182] Kaneko, A.; Yoshimoto, K., On a 2-factor with a specified edge in a graph satisfying the ore condition, Discrete math., 257, 445-461, (2002) · Zbl 1008.05118
[183] M. Kano, Graph factors with given properties, Graph Theory, Singapore, 1983, Lecture Notes in Mathematics, vol. 1073, Springer, Berlin, 1984, pp. 161-168.
[184] Kano, M., \([a, b]\)-factorization of a graph, J. graph theory, 9, 129-146, (1985) · Zbl 0587.05050
[185] Kano, M., \([a, b]\)-factorizations of nearly bipartite graphs, (), 471-474
[186] Kano, M., Factors of regular graphs, J. combin. theory ser. B, 41, 27-36, (1986) · Zbl 0591.05057
[187] Kano, M., A sufficient condition for a graph to have \([a, b]\)-factors, Graphs combin., 6, 245-251, (1990) · Zbl 0746.05051
[188] Kano, M., Sufficient conditions for a graph to have factors, Discrete math., 80, 159-165, (1990) · Zbl 0727.05045
[189] Kano, M., Current results and problems on factors of graphs, (), 93-98
[190] Kano, M.; Katona, G., Odd subgraphs and matchings, Discrete math., 250, 265-272, (2002) · Zbl 0996.05099
[191] M. Kano, G. Katona, Structure theorem and algorithm on \((1, f)\)-odd subgraphs, Discrete Math., 2004, to appear. · Zbl 1116.05078
[192] Kano, M.; Saito, A., \([a, b]\)-factors of graphs, Discrete math., 47, 113-116, (1983) · Zbl 0526.05047
[193] Kano, M.; Tokushige, N., Binding numbers and \(f\)-factors of graphs, J. combin. theory ser. B, 54, 213-221, (1992) · Zbl 0772.05080
[194] Kapoor, A.; Rizzi, R., Edge-coloring bipartite graphs, J. algorithms, 34, 390-396, (2000) · Zbl 0948.68129
[195] Karoński, M., A review of random graphs, J. graph theory, 6, 349-389, (1982) · Zbl 0512.05052
[196] Karoński, M., Random graphs, (), 351-380 · Zbl 0845.05082
[197] Karp, R., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[198] Karp, R., On the computational complexity of combinatorial problems, Networks, 5, 45-68, (1975) · Zbl 0324.05003
[199] Katerinis, P., Some results on the existence of \(2 n\)-factors in terms of vertex deleted subgraphs, Ars combin., 16-B, 271-277, (1983) · Zbl 0539.05049
[200] Katerinis, P., Some conditions for the existence of \(f\)-factors, J. graph theory, 9, 513-521, (1985) · Zbl 0664.05047
[201] Katerinis, P., A chvátal – erdős condition for an \(r\)-factor in a graph, Ars combin., 20, 185-191, (1985) · Zbl 0593.05053
[202] Katerinis, P., Two sufficient conditions for a 2-factor in a bipartite graph, J. graph theory, 11, 1-6, (1987) · Zbl 0651.05053
[203] Katerinis, P., Toughness of graphs and the existence of factors, Discrete math., 80, 81-92, (1990) · Zbl 0739.05047
[204] Katerinis, P., Minimum degree of bipartite graphs and the existence of \(k\)-factors, Graphs combin., 6, 253-258, (1990) · Zbl 0723.05098
[205] Katerinis, P.; Tsikopoulos, N., Minimum degree and \(F\)-factors in graphs, New Zealand J. math., 29, 33-40, (2000) · Zbl 0953.05062
[206] Katerinis, P.; Tsikopoulos, N., Independence number, connectivity and \(f\)-factors, Utilitas math., 57, 81-95, (2000) · Zbl 0962.05047
[207] Katerinis, P.; Woodall, D., Binding numbers of graphs and the existence of \(k\)-factors, Quart. J. math., 38, 221-228, (1987) · Zbl 0639.05050
[208] Kawarabayashi, K., \(K_4^-\)-factor in a graph, J. graph theory, 39, 111-128, (2002) · Zbl 0992.05059
[209] Kawarabayashi, K.; Matsuda, H.; Oda, Y.; Ota, K., Path factors in cubic graphs, J. graph theory, 39, 188-193, (2002) · Zbl 1176.05064
[210] Kelmans, A., Optimal packing of induced stars in a graph, Discrete math., 173, 97-127, (1997) · Zbl 0887.05041
[211] Z. Király, \(C_4\)-free f-factors in bipartite graphs, Egerváry research group on combinatorial optimization, Technical Report 2001-13, Budapest, Hungary, November, 1999.
[212] Kirkpatrick, D.; Hell, P., On the completeness of a generalized matching problem, (), 240-245 · Zbl 1282.68182
[213] Kirkpatrick, D.; Hell, P., On the complexity of general graph factor problems, SIAM J. comput., 12, 601-609, (1983) · Zbl 0525.68023
[214] Kleitman, D.; Wang, D., Algorithms for constructing graphs and digraphs with given valences and factors, Discrete math., 6, 79-88, (1973) · Zbl 0263.05122
[215] Kocay, W.; Stone, D., Balanced network flows, Bull. inst. combin. appl., 7, 17-32, (1993) · Zbl 0804.05057
[216] König, D., Über graphen und ihre andwendung auf determinantentheorie und mengenlehre, Math. ann., 77, 453-465, (1916) · JFM 46.0146.03
[217] König, D., Graphok és alkalmazásuk a determinánsok és a halmazok elméletére, Math. termész. ért, 34, 104-119, (1916) · JFM 46.1451.03
[218] König, D., Graphs and matrices, Mat. fiz. lapok, 38, 116-119, (1931), (in Hungarian) · JFM 57.1340.04
[219] König, D., Über trennende knotenpunkte in graphen (nebst. anwendungen auf determinanten und matrizen), Acta sci. math. (Szeged), 6, 155-179, (1933) · Zbl 0007.32901
[220] Kotani, K., Factors and connected induced subgraphs, Graphs combin., 17, 511-515, (2001) · Zbl 1010.05063
[221] Kotzig, A., On the theory of finite graphs with a linear factor, I, Mat.-fyz. časopis slovensk. akad. vied, 9, 73-91, (1959), (Slovak)
[222] Kotzig, A.; Rosa, A., Decomposition of complete graphs into isomorphic factors with a given diameter, Bull. London math. soc., 7, 51-57, (1975) · Zbl 0308.05128
[223] Kouider, M.; Mahéo, M., Connected \([a, b]\)-factors in graphs, Combinatorica, 22, 71-82, (2002) · Zbl 0989.05087
[224] M. Kouider, P. Vestergaard, Survey on connected factors in graphs, Graphs Combin. 21 (2005) 1-26. · Zbl 1066.05110
[225] Kundu, S., The \(k\)-factor conjecture is true, Discrete math., 6, 367-376, (1973) · Zbl 0278.05115
[226] Lan, J.; Chen, W.-K., On \(f\)-factors of a graphs, J. franklin inst., 320, 55-62, (1985) · Zbl 0615.05046
[227] Las Vergnas, M., A note on matchings in graphs, colloque sur la théorie des graphes (Paris, 1974), Cahiers centre études recherche opér., 17, 257-260, (1975) · Zbl 0315.05123
[228] Las Vergnas, M., An extension of Tutte’s 1-factor theorem, Discrete math., 23, 241-255, (1978) · Zbl 0404.05048
[229] Lenkewitz, U.; Volkmann, L., Neighbourhood and degree conditions for the existence of regular factors, Ars combin., 42, 33-47, (1996) · Zbl 0856.05079
[230] Li, G.; Liu, Z., On connected factors in \(K_{1, 3}\)-free graphs, Acta math. appl. sinica, 14, 43-47, (1998) · Zbl 0929.05071
[231] Li, G.; Zhu, B.; Chen, C., On connected \([k, k + 1]\)-factors in claw-free graphs, Ars combin., 62, 207-219, (2002) · Zbl 1071.05559
[232] Li, J., A neighborhood condition for graphs to have \([a, b]\)-factors, J. math. study, 35, 371-375, (2002) · Zbl 1015.05502
[233] Li, J., On neighborhood condition for graphs to have \([a, b]\)-factors, Discrete math., 260, 217-221, (2003) · Zbl 1013.05064
[234] Li, J.; Deng, H., Sufficient conditions for the existence of fractional factors of graphs, J. nat. sci. hunan norm. univ., 26, 25-28, (2003) · Zbl 1055.05121
[235] Li, Y.; Kano, M.; Mao-cheng, C., A \([k, k + 1]\)-factor containing given Hamiltonian cycle, Sci. China ser. A, 41, 933-938, (1998) · Zbl 0917.05062
[236] Li, Y.; Kano, M.; Mao-cheng, C., A \([k, k + 1]\)-factor containing given Hamiltonian cycle, Electron. J. combin., 6, (1999), Research Paper 4, 8pp (electronic)
[237] Li, Y.; Mao-cheng, C., A degree condition for the existence of connected factors, Australas. J. combin., 14, 77-83, (1996) · Zbl 0860.05059
[238] Li, Y.; Mao-cheng, C., A degree condition for a graph to have \([a, b]\)-factors, J. graph theory, 27, 1-6, (1998) · Zbl 0891.05057
[239] Lindner, C.; Mendelsohn, E.; Rosa, A., On the number of 1-factorizations of the complete graph, J. combin. theory ser. B, 20, 265-282, (1976) · Zbl 0293.05156
[240] Erratum: on defect-d matching in graphs, Discrete Math. 14 (1976) 203. · Zbl 0304.05120
[241] Liu, G., On f-covered graphs, Seventeenth manitoba conference on numerical mathematics and computing (winnipeg, MB, 1987), congr. numer., 61, 81-86, (1988)
[242] Liu, G., On \((g, f)\)-covered graphs, Acta math. sci. (English edition), 8, 181-184, (1988) · Zbl 0682.05051
[243] Liu, G., On \([a, b]\)-covered graphs, J. combin. math. combin. comput., 5, 14-22, (1989) · Zbl 0678.05047
[244] Liu, G.; Zhang, L., Maximum fractional \((0, f)\)-factors of graphs, Math. applic. (Wuhan), 13, 31-35, (2000) · Zbl 1016.05061
[245] Liu, G.; Zhang, L., Fractional \((g, f)\)-factors of graphs, Acta math. sci. ser. B (English edition), 21, 541-545, (2001) · Zbl 0989.05086
[246] Liu, Y.; Liu, G., The fractional matching numbers of graphs, Networks, 40, 228-231, (2002) · Zbl 1016.05060
[247] M. Loebl, S. Poljak, Subgraph packing—a survey, Topics in Combinatorics and Graph Theory (Oberwolfach, 1990), Physica, Heidelberg, 1990, pp. 491-503. · Zbl 0768.05078
[248] Lonc, Z., On the complexity of some edge-partition problems for graphs, Discrete appl. math., 70, 177-183, (1996) · Zbl 0860.05061
[249] Lovász, L., On decomposition of graphs, Studia sci. math. hungar., 1, 237-238, (1966) · Zbl 0151.33401
[250] Lovász, L., Subgraphs with prescribed valencies, J. combin. theory, 8, 391-416, (1970) · Zbl 0198.29201
[251] Lovász, L., Valencies of graphs with 1-factors, Period. math. hungar., 5, 149-151, (1974) · Zbl 0286.05126
[252] Lovász, L., A homology theory for spanning trees of a graph, Acta math. acad. sci. hungar., 30, 241-251, (1977) · Zbl 0403.05040
[253] L. Lovász, M. Plummer, Matching Theory, North-Holland Mathematics Studies, vol. 121, Annals of Discrete Mathematics, vol. 29, North-Holland Publishing Co., Amsterdam; Akadémiai Kiadó (Publishing House of the Hungarian Academy of Sciences), Budapest, 1986.
[254] Ma, S.; Wallis, W.; Wu, J., The complexity of the clique partition number problem, 19th southeastern conference on combinatorics, graph theory, and computing (baton rouge, LA, 1988), Congr. numer., 67, 59-66, (1988)
[255] Ma, Y.; Liu, G., Isolated toughness and the existence of fractional factors, Acta math. appl. sin., 26, 133-140, (2003) · Zbl 1016.05049
[256] Mahmoodian, E., On factors of a graph, Canad. J. math., 29, 438-440, (1977) · Zbl 0329.05119
[257] Mao-cheng, C., \([a, b]\)-factorizations of graphs, J. graph theory, 15, 283-301, (1991) · Zbl 0765.05076
[258] Mao-cheng, C., A degree condition for the existence of connected \([k, k + 1]\)-factors, Systems sci. math. sci., 8, 364-368, (1995) · Zbl 0851.05083
[259] Mao-cheng, C., Connected \([k, k + 1]\)-factors of graphs, Discrete math., 169, 1-16, (1997) · Zbl 0879.05061
[260] Marková, I., Decomposition of complete graphs into factors with diameter two, Acta math. univ. Comenian., 56/57, 235-241, (1989) · Zbl 0759.05073
[261] Martin, N., Complete bipartite factorisations by complete bipartite graphs, Discrete math., 167/168, 461-480, (1997) · Zbl 0878.05066
[262] Martin, N., Complete bipartite factorisations of \(K_{n, n}\), Discrete math., 266, 353-375, (2003) · Zbl 1020.05057
[263] Matsuda, H., A neighborhood condition for graphs to have \([a, b]\)-factors, Discrete math., 224, 289-292, (2000) · Zbl 0966.05062
[264] Matsuda, H., A neighborhood condition for graphs to have \([a, b]\)-factors. II, Graphs combin., 18, 763-768, (2002) · Zbl 1009.05111
[265] Matsuda, H., Degree conditions for the existence of \([k, k + 1]\)-factors containing a given Hamiltonian cycle, Australas. J. combin., 26, 273-281, (2002) · Zbl 1022.05063
[266] Matsuda, H., Degree conditions for Hamiltonian graphs to have \([a, b]\)-factors containing a given Hamiltonian cycle, Discrete math., 280, 241-250, (2004) · Zbl 1041.05044
[267] H. Matsuda, Regular factors containing a given Hamiltonian cycle, preprint, 2003.
[268] McCarthy, P., Matchings in graphs II, Discrete math., 11, 141-145, (1975) · Zbl 0299.05115
[269] P. McCarthy, Matchings in graphs. III. Infinite graphs, Theory and Applications of Graphs (Proceedings of International Conference Western Michigan University, Kalamazoo, Michigan 1976), Lecture Notes in Mathematics, vol. 642, Springer, Berlin, 1978, pp. 384-393.
[270] McCarthy, P., Matchings in infinite graphs, Czechoslovak math. J., 28, 245-251, (1978) · Zbl 0392.05058
[271] McDiarmid, C.; Reed, B., Linear arboricity of random regular graphs, Random structures algorithms, 1, 443-445, (1990) · Zbl 0744.05048
[272] McDiarmid, C.; Reed, B., Almost every graph can be covered by \(\lceil \Delta / 2 \rceil\) linear forests, Combin. probab. comput., 4, 257-268, (1995) · Zbl 0852.05069
[273] Mendelsohn, E.; Rosa, A., On some properties of 1-factorizations of complete graphs, Congress. numer., XXIII-XXIV, 739-752, (1979)
[274] Mendelsohn, E.; Rosa, A., One-factorizations of the complete graphs—a survey, J. graph theory, 9, 43-65, (1985) · Zbl 0587.05049
[275] S. Micali, V. Vazirani, An \(O(| V |^{1 / 2} | E |)\) algorithm for finding maximum matchings in general graphs, Proceedings of the 21st Annual Symposium on Foundation in Computer Science (Syracuse) 1980, pp. 17-27.
[276] Molloy, M., The probabilistic method, Algorithms combin., 16, 1-35, (1998) · Zbl 0918.05092
[277] Molloy, M.; Reed, B., Graph colouring and the probabilistic method, (2002), Springer Berlin · Zbl 0987.05002
[278] Molloy, M.; Robalewska, H.; Robinson, R.; Wormald, N., 1-factorizations of random regular graphs, Random structures algorithms, 10, 305-321, (1997) · Zbl 0974.05062
[279] Mühlbacher, J., F-factors of graphs: a generalized matching problem, Inform. process. lett., 8, 207-214, (1979) · Zbl 0426.05043
[280] Mühlbacher, J.; Steinparz, F.; Tinhofer, G., On certain classes of fractional matchings, Discrete appl. math., 9, 235-244, (1984) · Zbl 0545.90099
[281] Y. Nam, Ore-type condition for the existence of connected factors, preprint, February, 2000.
[282] Nešetřil, J.; Poljak, J., On the complexity of the subgraph problem, Comment. math. univ. carolin., 26, 415-419, (1985) · Zbl 0571.05050
[283] Niedermeyer, F., f-optimal factors of infinite graphs, Discrete math., 95, 231-254, (1991) · Zbl 0759.05075
[284] Niedermeyer, F.; Podewski, K-P., Matchable infinite graphs, J. combin. theory ser. B, 62, 213-227, (1994) · Zbl 0807.05063
[285] Niepel, L., On decompositions of complete graphs into factors with given diameters and radii, Math. slovaca, 30, 3-11, (1980) · Zbl 0422.05045
[286] Niessen, T., Nash-Williams conditions and the existence of k-factors, Ars combin., 34, 251-256, (1992) · Zbl 0770.05083
[287] Niessen, T., A characterization of graphs having all \((g, f)\)-factors, J. combin. theory ser. B, 72, 152-156, (1998) · Zbl 0888.05048
[288] Niessen, T.; Randerath, B., Regular factors of simple regular graphs and factor-spectra, Discrete math., 185, 89-103, (1998) · Zbl 0958.05114
[289] Niessen, T.; Volkmann, L., Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree, J. graph theory, 14, 225-246, (1990) · Zbl 0704.05041
[290] Nishimura, T., Independence number, connectivity and degree factors, SUT J. math., 25, 79-87, (1989) · Zbl 0697.05047
[291] Nishimura, T., Independence number connectivity and r-factors, J. graph theory, 13, 63-69, (1989) · Zbl 0682.05053
[292] Nishimura, T., Regular factors of line graphs. II, Math. japon., 36, 1033-1040, (1991) · Zbl 0764.05075
[293] Nishimura, T., A degree condition for the existence of k-factors, J. graph theory, 16, 141-151, (1992) · Zbl 0781.05039
[294] Nishimura, T., Degree factors of line graphs, Ars combin., 38, 149-159, (1994) · Zbl 0824.05052
[295] Nishimura, T., Component factors and induced subgraphs, J. graph theory, 22, 305-308, (1996) · Zbl 0858.05090
[296] T. Nishizeki, Lower bounds on the cardinality of the maximum matchings of graphs, Proceedings of Ninth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic University, Boca Raton, FL, 1978), Congress. Numer. XXI, Utilitas Math. Winnipeg, Man., 1978, pp. 527-547. · Zbl 0413.05020
[297] Nishizeki, T., On the relationship between the genus and the cardinality of the maximum matchings of a graph, Discrete math., 25, 149-156, (1979) · Zbl 0418.05033
[298] Orlin, J., Dynamic matchings and quasi-dynamic fractional matchings I and II, Networks, 13, 551-580, (1983) · Zbl 0526.90090
[299] Palumbíny, D., On a certain type of decompositions of complete graphs into factors with equal diameters, Mat. časopis sloven. akad. vied, 22, 235-242, (1972) · Zbl 0247.05160
[300] Palumbíny, D., On decompositions of complete graphs into factors with equal diameters, Boll. un. mat. ital., 7, 4, 420-428, (1973) · Zbl 0264.05124
[301] Palumbíny, D.; Znám, S., On decompositions of complete graphs into factors with given radii, Mat. časopis sloven. akad. vied, 23, 306-316, (1973) · Zbl 0269.05121
[302] Perkovic, L.; Reed, B., Edge coloring regular graphs of high degree, Discrete math., 165/166, 567-578, (1997) · Zbl 0902.05030
[303] Péroche, B., Complexité de l’arboricité linéaire d’un graphe, II., RAIRO rech. opér., 19, 293-300, (1985) · Zbl 0608.05029
[304] Petersen, J., Die theorie der regulären graphen, Acta math., 15, 193-220, (1891) · JFM 23.0115.03
[305] Peterson, P.; Loui, M., The general maximum matching algorithm of micali and Vazirani, Algorithmica, 3, 511-533, (1988) · Zbl 0648.68077
[306] Picouleau, C., Complexity of the Hamiltonian cycle in regular graph problem, Theoret. comput. sci., 131, 463-473, (1994) · Zbl 0809.68091
[307] Planthold, M.; Tipnis, S., Regular multigraphs of high degree are 1-factorizable, Proc. London math. soc., 44, 393-400, (1991) · Zbl 0760.05073
[308] Plantholt, M.; Tipnis, S., All regular multigraphs of even order and high degree are 1-factorable, Electron. J. combin., 8, #R41, (2001) · Zbl 0981.05079
[309] Plesník, J., Complexity of decomposing graphs into factors with given diameters or radii, Math. slovaca, 32, 379-388, (1982) · Zbl 0505.05052
[310] Plesník, J., A note on the complexity of finding regular subgraphs, Discrete math., 49, 161-167, (1984) · Zbl 0567.05029
[311] Plummer, M., Extending matchings in graphs: a survey, Discrete math., 127, 277-292, (1994) · Zbl 0798.05040
[312] Plummer, M., Extending matchings in graphs: an update, Congr. numer., 116, 3-32, (1996) · Zbl 0902.05059
[313] Podewski, K.; Steffens, K., Injective choice functions for countable families, J. combin. theory ser. B, 21, 40-46, (1976) · Zbl 0357.04017
[314] Pulleyblank, W., Fractional matchings and the edmonds – gallai theorem, Discrete appl. math., 16, 51-58, (1987) · Zbl 0637.05019
[315] Pulleyblank, W., Matchings and extensions, handbook of combinatorics, (1995), Elsevier Amsterdam, pp. 179-232 · Zbl 0866.05048
[316] Quinn, S., Isomorphic factorizations of complete equipartite graphs, J. graph theory, 7, 285-310, (1983) · Zbl 0516.05045
[317] Rado, R., Factorization of even graphs, Quart. J. math. Oxford ser., 20, 94-104, (1949) · Zbl 0032.31601
[318] Rizzi, R., Finding 1-factors in bipartite regular graphs and edge-coloring bipartite graphs, SIAM J. discrete math., 15, 283-288, (2002) · Zbl 1007.05082
[319] Robalewska, H., 2-factors in random regular graphs, J. graph theory, 23, 215-224, (1996) · Zbl 0874.05048
[320] A. Robertshaw, k-factors and extendability in bipartite graphs, preprint, November, 2002.
[321] Rodger, C., Graph decompositions, Matematiche (Catania), 45, 119-139, (1990) · Zbl 0735.05066
[322] A. Ruciński, Subgraphs of random graphs: a general approach, Random Graphs ’83 (Poznań, 1983), North-Holland Mathematical Studies, vol. 118, North-Holland, Amsterdam, 1985, pp. 221-229.
[323] Ryjáček, Z.; Saito, A.; Schelp, R.H., 2-factors and cycle coverings in claw-free graphs, J. graph theory, 32, 109-117, (1999) · Zbl 0932.05045
[324] Saito, A., One-factors and k-factors, Discrete math., 91, 323-326, (1991) · Zbl 0759.05076
[325] Saito, A.; Watanabe, M., Partitioning graphs into induced stars, Ars combin., 36, 3-6, (1993) · Zbl 0794.05107
[326] Schönheim, J.; Bialostocki, A., Decomposition of \(K_n\) into subgraphs of prescribed type, Arch. math. (basel), 31, 105-112, (1978/79) · Zbl 0379.05049
[327] A. Schrijver, Bounds on permanents, and the number of 1-factors and 1-factorizations of bipartite graphs, Surveys in Combinatorics, London Mathematical Society, Lecture Note Series, vol. 82, 1983, pp. 107-134. · Zbl 0529.05048
[328] Schrijver, A., Bipartite edge colouring in \(\operatorname{O}(\operatorname{\Delta} m)\) time, SIAM J. comput., 28, 841-846, (1998)
[329] Schrijver, A., Counting 1-factors in regular bipartite graphs, J. combin. theory ser. B, 72, 122-135, (1998) · Zbl 0905.05060
[330] Schrijver, A.; Valiant, W., On lower bounds for permanents, Nederl. akad. wetensch. indag. math., 42, 425-427, (1980) · Zbl 0451.15009
[331] Shamir, E.; Upfal, E., On factors in random graphs, Israel J. math., 39, 296-302, (1981) · Zbl 0475.05067
[332] Shamir, E.; Upfal, E., One-factor in random graphs based on vertex choice, Discrete math., 41, 281-286, (1982) · Zbl 0495.05058
[333] Stanton, R.; Goulden, I., Graph factorization, general triple systems, and cyclic triple systems, Aequationes math., 22, 1-28, (1981) · Zbl 0466.05011
[334] Steffens, K., Matchings in countable graphs, Canad. J. math., 29, 165-168, (1977) · Zbl 0324.05122
[335] Steffens, K., Maximal tight sets and the edmonds – gallai decomposition for matchings, Combinatorica, 5, 359-365, (1985) · Zbl 0608.05064
[336] Steffens, K., Faktoren in unendlichen graphen, Jahresber. Deutsch. math.-verein., 87, 127-137, (1985) · Zbl 0579.05042
[337] K. Steffens, The f-factors of countable graphs, Grüne Reihe Preprint Series, No. 233 (University of Hannover), 1989.
[338] F. Steinparz, On the existence of F factors, Conference on Graphtheoretic Concepts in Computer Science (7th: 1981: Linz, Austria) Hanser, Munich, 1982, pp. 61-73.
[339] D. Sumner, On Tutte’s factorization theorem, Graphs and Combinatorics (Proc. Capital Conf., George Washington University, Washington, DC, 1973), vol. 406, Springer, Berlin, 1974, pp. 350-355.
[340] Sumner, D., 1-factors and anti-factor sets, J. London math. soc., 13, 351-359, (1976) · Zbl 0338.05118
[341] Tashkinov, V., 3-regular subgraphs of 4-regular graphs (Russian), Mat. zametki, 36, 239-259, (1984), English transl.: Math. Notes 6 (1984) 612-623
[342] Thomassen, C., A remark on the factor theorems of lovász and Tutte, J. graph theory, 5, 441-442, (1981) · Zbl 0465.05055
[343] Thomassen, C., Graph decomposition with constraints on the connectivity and minimum degree, J. graph theory, 7, 165-167, (1983) · Zbl 0515.05045
[344] Tokuda, T., A degree condition for the existence of \([a, b]\)-factors in \(K_{1, n}\)-free graphs, Tokyo J. math., 21, 377-380, (1998) · Zbl 0916.05058
[345] Tokushige, N., Binding number and minimum degree for k-factors, J. graph theory, 13, 607-617, (1989) · Zbl 0693.05052
[346] Tomová, E., Decomposition of complete bipartite graphs into factors with given radii, Math. slovaca, 27, 231-237, (1977) · Zbl 0357.05067
[347] E. Tomová, Decompositions of complete bipartite graphs into factors with given diameters and radii, Graphs and Other Combinatorial Topics (Prague, 1982), Teubner-Texte Math., vol. 59, Teubner, Leipzig, 1983, pp. 325-327.
[348] Tomová, E., Decomposition of complete bipartite graphs into factors with given diameters and radii, Math. slovaca, 34, 249-253, (1984) · Zbl 0599.05048
[349] Topp, J.; Vestergaard, P., Odd factors of a graph, Graphs combin., 9, 371-381, (1993) · Zbl 0795.05115
[350] Truszczynski, M., Linear arboricity of graphs, Math. slovaca, 36, 105-108, (1986) · Zbl 0664.05049
[351] Tutte, W., The factorization of linear graphs, J. London math. soc., 22, 107-111, (1947) · Zbl 0029.23301
[352] Tutte, W., The factors of graphs, Canad. J. math., 4, 314-328, (1952) · Zbl 0049.24202
[353] Tutte, W., A short proof of the factor theorem for finite graphs, Canad. J. math., 6, 347-352, (1954) · Zbl 0055.17102
[354] Tutte, W., On the problem of decomposing a graph into n connected factors, J. London math. soc., 36, 221-230, (1961) · Zbl 0096.38001
[355] Tutte, W., Spanning subgraphs with specified valencies, Discrete math., 9, 97-108, (1974) · Zbl 0284.05123
[356] Tutte, W., Graph factors, Combinatorica, 1, 79-97, (1981) · Zbl 0494.05046
[357] J. Uhry, Sur le probléme du couplage maximal, RAIRO 9 (1975), V-3, 13-20. · Zbl 0357.90071
[358] Valiant, L., The complexity of computing the permanent, Theoret. comput. sci., 8, 189-201, (1979) · Zbl 0415.68008
[359] Valiant, L., The complexity of enumeration and reliability problems, SIAM J. comput., 8, 410-421, (1979) · Zbl 0419.68082
[360] van der Waerden, B., Problem 45, Jahresber. Deutsch. math.-verein., 35, 117, (1926)
[361] Vazirani, V., A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V} E)\) general graph maximum matching algorithm, Combinatorica, 14, 71-109, (1994) · Zbl 0806.05058
[362] Volkmann, L., Regular graphs, regular factors, and the impact of Petersen’s theorems, Jahresber. Deutsch. math.-verein., 97, 19-42, (1995) · Zbl 0822.05053
[363] Wallis, W., One-factorizations, (1997), Kluwer Academic Publishers Group Dordrecht · Zbl 0863.05064
[364] Wang, J., Isomorphic factorizations of complete equipartite graphs – the proof of the harary – robinson – wormald conjecture, Sci. sinica ser. A, 25, 1152-1164, (1982) · Zbl 0513.05047
[365] Woodall, D., k-factors and neighbourhoods of independent sets in graphs, J. London math. soc., 41, 385-392, (1990) · Zbl 0659.05070
[366] Wormald, N., Isomorphic factorizations. VII. regular graphs and tournaments, J. graph theory, 8, 117-122, (1984) · Zbl 0532.05048
[367] Wu, J.-L., On the linear arboricity of planar graphs, J. graph theory, 31, 129-134, (1999) · Zbl 0933.05056
[368] Xu, B.; Liu, Z.; Tokuda, T., Connected factors in \(K_{1, n}\)-free graphs containing a \((g, f)\)-factor, Graphs combin., 14, 393-395, (1998) · Zbl 0910.05051
[369] Yan, G., Some new results on \((g, f)\)-factorizations of graphs, J. combin. math. combin. comput., 18, 177-185, (1995) · Zbl 0833.05065
[370] Yan, G., Some new results on \((g, f)\)-factorizations of graphs, Math. appl. (Wuhan), 9, 117-120, (1996), (in Chinese) · Zbl 0949.05516
[371] Yan, G.; Pan, J.; Wong, C.; Takuda, T., Decompositions of graphs into \((g, f)\)-factors, Graphs combin., 16, 117-126, (2000) · Zbl 0942.05058
[372] Yang, J.; Ma, Y.; Liu, G., Fractional \((g, f)\) factors of graphs, Appl. math. J. Chinese univ. ser. A, 16, 385-390, (2001) · Zbl 0991.05087
[373] Yu, Q., On barrier sets of star-factors, Graphs combin., 6, 71-76, (1990) · Zbl 0735.05070
[374] Yu, Q., On star-factor covered graphs, J. math. (Wuhan), 11, 450-454, (1991) · Zbl 0761.05076
[375] Yu, Q., Counting the number of star-factors in graphs, J. combin. math. combin. comput., 23, 65-76, (1997) · Zbl 0872.05043
[376] Zhang, C.-Q.; Zhu, Y., Factorizations of regular graphs, J. combin. theory ser. B, 56, 74-89, (1992) · Zbl 0711.05036
[377] Zhang, L., Every 4-regular simple graph contains a 3-regular subgraph, J. Changsha railway inst., 1, 130-154, (1985) · Zbl 0566.05048
[378] Zhang, L.; Liu, G., Fractional k-factors of graphs, J. systems sci. math. sci., 21, 88-92, (2001), (in Chinese) · Zbl 0985.05039
[379] Znám, S., On a conjecture of Bollobás and bosák, J. graph theory, 6, 139-146, (1982) · Zbl 0497.05049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.