Plummer F Factor Survey

Discrete Mathematics 307 (2007) 791 – 821
www.elsevier.com/locate/disc
Perspectives
Graph factors and factorization: 1985–2003: A survey
Michael D. Plummer
Department of Mathematics, Vanderbilt University, Nashville, Tennessee 37240, USA
Received 29 January 2004; received in revised form 13 September 2004; accepted 22 November 2005
Available online 16 October 2006
Dedicated to the memory of Peter Owens
Abstract
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, R. Graham, Recent results in graph decompositions, London Mathematical Society, Lecture Note Series, vol. 52,
Cambridge University Press, 1981, pp. 103–123; J. Akiyama, M. Kano, Factors and factorizations of graphs—a survey, J. Graph
Theory 9 (1985) 1–42; L. Volkmann, Regular graphs, regular factors, and the impact of Petersen’s theorems, Jahresber. Deutsch.
Math.-Verein. 97 (1995) 19–42] as well as an entire book on graph decompositions [J. Bosák, Decompositions of Graphs, Kluwer
Academic Publishers Group, Dordrecht, 1990]. Our purpose here is to concentrate primarily on surveying the developments of the
last 15–20 years in this exponentially growing field.
© 2006 Elsevier B.V. All rights reserved.
Keywords: Factor; Factorization; Matching
1. Introduction
A subgraph H of a graph (multigraph, general graph) G, is a factor of G if H is a spanning subgraph of G. This

definition is sufficiently general so as to include such prominent problems in graph theory as edge coloring and Hamilton
cycles to name but two. Although both of these problems will be mentioned in our survey, we shall concentrate on
other areas of graph factors, leaving the reader to consult existing surveys on these two topics (cf. [108,109,126,127]).
We shall take as our departure point an excellent survey of graph factors up to 1985 written by Akiyama and
Kano [12].
Hence we shall concentrate on works published since their paper appeared, although we shall certainly mention
some of the basic results on factors obtained prior to the Akiyama–Kano paper, but which form the basis of more recent
work.
Akiyama and Kano divided the field of graph factors into two classes of problems. They named these two classes
degree factor problems and component factor problems and we shall follow their lead in this.
A factor F described in terms of its degrees will be called a degree factor. For example, if a factor F has all of its
degrees equal to 1, it is called a 1-factor (or a perfect matching). On the other hand, if the factor is described via some
other graphical concept, it is called a component factor. For example, if each component of the factor F is a tree, F is
E-mail address: [email protected].
0012-365X/$ - see front matter © 2006 Elsevier B.V. All rights reserved.
doi:10.1016/j.disc.2005.11.059
792 Michael D. Plummer / Discrete Mathematics 307 (2007) 791 – 821
a component factor. We hasten to observe that these two classes are not disjoint. For example, finding a 1-factor (i.e.,
a factor in which each vertex has degree one) and finding a factor each component of which is an edge amounts to the
same thing.
If the edge set of a graph G can be represented as the edge-disjoint union of factors F1 , F2 , . . . , Fk , we shall refer
to {F1 , F2 , . . . , Fk } as a factorization of graph G.
There is a vast body of work on factors and factorizations and this topic has much in common with other areas of
study in graph theory. For example, factorization significantly overlaps the topic of edge coloring. Indeed, any color
class of a proper edge coloring of a graph is just a matching. Moreover, the Hamilton cycle problem can be viewed as
the search for a connected factor in which the degree of each vertex is exactly two.
We will treat factors of finite undirected graphs only. However, a number of papers dealing with infinite graph factors
and directed graph factors are included in our reference list. We do not discuss these results here, but instead refer the
interested reader to [317,2–8,49,168,268–270,313,334–337,283,284].
Let us now present some of the basic definitions, notation and terminology used in this paper. Other terminology
will be introduced as it naturally occurs in the text. We denote the vertex set and the edge set of a graph G by V (G)
and E(G), respectively. In this paper, all graphs will be considered simple, unless otherwise specified. That is to say,
there is at most one edge joining any pair of vertices. By multigraph we mean that there may be multiple edges joining
the same pair of vertices. If graph G admits a vertex partition V (G) = V1 ∪ · · · ∪ Vj such that every edge of G joins
two different Vi ’s, we say that G is multipartite. If j = 2, we say that G is bipartite. The complete bipartite graph Km,n
has m vertices in one class, n in the other and all pairs of vertices from different classes are joined by an edge.
A path in graph G is an alternating sequence of distinct vertices and edges beginning and ending with vertices in
which each edge joins the vertex before it to the one following it. The length of a path P is the number of edges in P.
Pi will designate a path containing exactly i vertices. A graph G is connected if every pair of vertices in G are joined
by a path in G. Otherwise, it is disconnected. If every pair of vertices are joined by an edge, we say that the graph is
complete and if, in addition, |V (G)| = n, we denote this graph by Kn .
Graph H is a subgraph of graph G if V (H ) ⊆ V (G) and E(H ) ⊆ E(G). A subgraph H of G spans G if V (H )=V (G).
A subgraph H of G is induced if every pair of vertices in H which are adjacent in G are also adjacent in H. An induced
subgraph isomorphic to the complete bipartite graph K1,3 is called a claw. A graph containing no K1,3 as an induced
subgraph is said to be claw-free. More generally, if H and G are graphs and G does not contain H as an induced subgraph,
we shall say that G is H-free. A component of G is a maximal connected subgraph of G. A set of vertices S ⊆ V (G)
is a cutset of a connected graph G if G − S is disconnected. The cardinality of any smallest cutset in G is called the
connectivity of G and is denoted by (G). (As usual, we define (G) = 0 if G is disconnected and (Kn ) = n − 1 for
the complete graph Kn .) Similarly, the cardinality of any smallest set of edges in G the removal of which disconnects
the graph is called the edge-connectivity of G and is denoted by (G). If e is an edge in a connected graph G such that
G − e is disconnected, we say that e is a bridge or cutedge.
The degree of a vertex v, denoted degG (v), or simply deg(v), when the underlying graph is understood, is the number
of edges incident with the vertex. The minimum degree in graph G will be denoted by (G) and the maximum degree
by (G). A sequence {d1 , . . . , dn } of non-negative integers is said to be graphical if there is a graph G the vertex set of
which can be labelled so as to have degG (vi ) = di , for i = 1, . . . , n. A graph is r-regular if the degree of each vertex in
G is r and the graph is regular if it is r-regular for some r. A set of vertices is independent if no two of its members are
joined by an edge. The cardinality of any largest independent set of vertices in G is called the independence number of
G and is denoted by (G). A cycle in G consists of a path of length at least two together with an edge joining the first
and last vertices of the path. A cycle is Hamiltonian if it spans G. A cyclic component of G is a component which is a
cycle.
A set of edges in G is a matching if no two of them share an endvertex. A perfect matching (or 1-factor) in G is
a matching the edges of which span G. A (proper) edge coloring of graph G is an assignment of colors to its edges
such that all edges of the same color are a matching. The cardinality of any smallest set of colors such that G has a
proper edge coloring is called the edge-chromatic number (or chromatic index) of G and is denoted by (G). By a
classical result of Vizing, every graph G can be edge colored in at most (G) + 1 colors. Hence the set of all graphs is
naturally partitioned into two classes, Class 1 or Class 2, according as to whether (G) = (G) or (G) = (G) + 1,
respectively.
The (orientable) genus of a graph G, (G), is the smallest genus of any orientable surface in which G can be embedded
without edge crossings. The line graph of G, L(G), is the graph the vertex set of which is the edge set of G and two
Michael D. Plummer / Discrete Mathematics 307 (2007) 791 – 821 793
vertices of L(G) are adjacent if, as edges in G, they share a common endvertex. The complement of graph G, denoted
G, is the graph on the same vertex set as G, but in which two vertices are adjacent if and only if they are not adjacent
in G.
2. Degree factors
A factor F of graph G is an r-factor if the degree of each vertex in F is r. Easily the most studied of degree factors
are those in which r = 1, i.e., each component is a single edge.
2.1. 1-factors
The literature on matchings and 1-factors is vast in its own right and there already exist several sources surveying
many of the results in this area. (See, for example, [253,315].) Hence in the present work we shall concentrate mostly on
those properties of 1-factors and 1-factorizations which most naturally extend to analogous properties of more general
factors.
Historically, one of the first sufficient conditions for a 1-factor was discovered by Petersen [304] and today his result
is viewed by most as one of the seminal results in the study of graph factors.
Theorem 2.1 (Petersen [304]). Every 2-edge-connected 3-regular multigraph has a 1-factor (and hence also a
2-factor).
Petersen’s result was later generalized by Bäbler as follows:
Theorem 2.2 (Bäbler [29]). Every (r − 1)-edge-connected r-regular multigraph with an even number of vertices has
a 1-factor.
Certainly one of the most influential theorems in the study of 1-factors (at least in general, i.e., non-bipartite, graphs)
has been the seminal result called Tutte’s 1-factor Theorem.
Theorem 2.3 (Tutte [351]). A graph G has a 1-factor if and only if for each S ⊆ V (G), co (G − S) |S|, where
co (G − S) denotes the number of components of G − S which have an odd number of vertices.
One of the most popular areas of work involving 1-factors has been the search for interesting sufficient conditions
for their existence.
A topic which has gained considerable popularity in the last 30 years or so is the study of factor properties in
graphs which have certain forbidden (induced) subgraphs such as the claw. Sumner [339,340] and Las Vergnas [227]
independently proved the next theorem which is of this type.
Theorem 2.4. If G is a connected claw-free graph of even order, then G has a 1-factor.
Sumner extended this result as follows.
Theorem 2.5. If G is an n-connected graph of even order and G has no induced subgraph isomorphic to the bipartite
graph K1,n+1 , then G has a 1-factor.
A different type of subgraph condition sufficient for the existence of 1-factors was discovered by Fulkerson et al.
[119]; see also [256]. Graph G is said to have the odd cycle property if every pair of odd cycles in G either have a vertex
in common or are joined by an edge.
Theorem 2.6. If G is r-regular of even order and has the odd cycle property, then G has a 1-factor.
Yet another sufficient condition, this time topological, is given in the next result due to Nishizeki. Let (G) denote
the (orientable) genus of the graph G.
Theorem 2.7 (Nishizeki [296,297]). If G is a k-connected graph (k 4) of even order and if (G) < k(k − 2)/4, then
G has a 1-factor.
Two other graph parameters which have been considered in connection with 1-factors are toughness and binding
number. The toughness of graph G, denoted by tough (G), is defined to be +∞ when G is complete and otherwise
to be
min{|S|/c(G − S)|S ⊆ V (G)},
where the minimum is taken over all cutsets S ⊆ V (G) and c(G − S) denotes the number of components of G − S.
The next result follows immediately from Tutte’s 1-factor Theorem.
Corollary 2.8. If G is of even order and tough (G) 1, then G has a 1-factor.
The binding number of G, denoted bind (G), is defined to be

min{|N(X)|/|X||∅ = X ⊆ V (G) and N (X) = V (G)}.
The next theorem is due to Anderson [22] and can be regarded as a binding number result.
Theorem 2.9. Let G be a graph of even order. If, for all X ⊆ V (G),

|N(X)| min |V (G)|, 43 |X| − 23 ,
then G has a 1-factor.
The next result is due independently to Kundu [225] and Lovász [251].
Theorem 2.10. There exists a graph G having a 1-factor and degree sequence d1 , d2 , . . . , dn if and only if both the
sequences d1 , . . . , dn and d1 − 1, . . . , dn − 1 are graphical.
Highly symmetric graphs of even order are guaranteed to have 1-factors by the next result. (See [253, Theorem
5.5.24] for an extension of this result.)
Theorem 2.11 (Little et al. [240]). If G is a connected graph of even order the automorphism group of which acts
transitively on V (G), then G has a 1-factor containing any given edge.
There are many recent papers investigating the existence of 1-factors containing or excluding specified edge sets.
However, space does not permit us to treat these results and for the case of 1-factors, we direct the interested reader
to three survey articles on the subject [241,311,312]. For some sample sufficient conditions for the existence of other
types of factors containing a given edge or edges, see [56,83,182,320,264].
If graph G has exactly one 1-factor, then the following three facts are known about the structure of G. The first is
due to Kotzig [221], the second to Lovász [253] and the third to Hetyei (unpublished).
Theorem 2.12. Let G be connected and have a unique 1-factor. Then:
(a) G has a cutedge belonging to the 1-factor;

(b) G contains a vertex of degree log2 (|V (G)| + 1) ; and
(c) |E(G)|(|V (G)|/2)2 .
Gabow, et al. [120,121] invented an O(|E|log4 |V |) algorithm to decide whether a graph has a unique 1-factor and
to find it, if it exists.
Another problem concerning 1-factors which has attracted considerable interest is that of determining how many
there are. Let us denote by (G) the number of 1-factors in graph G. It has been shown that one can bound (G)
below by a certain matrix function called a Pfaffian. In the case when G is planar, the Pfaffian can be used to exactly
compute (G) in polynomial time. (For details, see [253, Section 8.3].)
The connectivity of the graph G can also be employed to yield a lower bound on (G) in some cases. A graph G is
said to be bicritical if G − x − y has a 1-factor for every choice of two different vertices x and y. (For further reading
on bicritical graphs, see [253].)
Theorem 2.13. If G is k-connected and has a 1-factor, then either

(a) G has at least k! 1-factors, or else
(b) G is bicritical.
It seems somewhat counterintuitive, perhaps, that bicritical graphs should be the exception here, but it has proven
much more difficult to bound (G) in the bicritical case. Study of the perfect matching polytope of G, PM(G), (see
[253]) can be utilized to give the bound in the next result.
Theorem 2.14. If G is bicritical, then (G) |V (G)|/2 + 1.
From the two preceding facts one has the following.
Theorem 2.15. If G is k-connected and contains a 1-factor, then there exists a function of k, p0 (k), such that if
|V (G)| p0 (k), then G has at least k! 1-factors.
In the special case of bipartite graphs, the history of 1-factors has two principal roots. The first is a result due to Hall
[135] and the second, a result due to König [218,219]. (In fact, it can be shown that these two results are equivalent.)
First we state Hall’s Theorem.
Theorem 2.16. Let G be a bipartite graph with vertex bipartition V (G) = A ∪ B. Then G has a matching of A into B
if and only if |N (X)| |X|, for all X ⊆ A.
An immediate consequence is the following even earlier result due to Frobenius [116] which is usually called the
Marriage Theorem.
Theorem 2.17. Let G be a bipartite graph with vertex bipartition V (G) = A ∪ B. Then G has a 1-factor matching A
onto B if and only if
(a) |A| = |B| and

(b) |N (X)||X|, for all X ⊆ A.
A subset C ⊆ V (G) is called a vertex cover of G if every edge of G has at least one endvertex in C. The size of
any smallest vertex cover in G is denoted by
(G) and called the vertex covering number of G. The size of any largest
matching in G is denoted by (G) and called the matching number of G. It is clear that in any graph G, (G)
(G).
However, if G is bipartite, König [218,219] proved the following.
Theorem 2.18. If G is bipartite, then (G) =

(G).
Since the above result asserts the equality of the maximum of one quantity and the minimum of another, it is often
referred to as a minimax theorem. Indeed, in more recent times, especially with the advent of linear programming, such
so-called minimax results have gained increasing importance. The study of minimax theorems is outside the scope of
this survey, but for an introduction to such ideas at least within the confines of graph theory, and for associated polytopal
ideas, the reader is referred to [253, Chapters 7 and 12].
For an arbitrary simple bipartite graph, the following lower bound for (G) is known.
Theorem 2.19 (Hall [134]). Let G be a simple bipartite graph with bipartition V (G) = A ∪ B and assume that for
each vertex in A has degree at least k. Then if G has at least one 1-factor, it has at least k! 1-factors.
If the bipartite graph G is regular, then we can obtain better bounds on the number of 1-factors. In the case of lower
bounds, an important idea from algebra is extremely useful. Let A = (aij ) be an n × n matrix.
The permanent of matrix A, denoted perA, is given by

per A = a1(1) a2(2) · · · an(n) ,
where the sum extends over all permutations of the set {1, . . . , n}.
Note that the only difference between the permanent and the more familiar notion of the determinant of a matrix is
that in the case of the permanent, each term is taken with a plus sign. There is a direct correspondence between binary
n × n matrices and simple bipartite graphs with bipartition V (G) = A ∪ B where |A| = |B| obtained as follows. Let
A = {a1 , . . . , an } and B = {b1 , . . . , bn } and suppose we identify the rows of an n × n binary matrix M with the elements
of A and the columns of M with the elements of B. Moreover, let us define the (i, j ) entry of M to be 1 if and only if
vertex ai is adjacent to vertex bj in G, and 0, otherwise. Then it is clear that per M = (G). Thus, at least in theory,
this gives an algorithm for computing exactly the number of 1-factors in a simple bipartite graph. However, in fact, the
problem of computing the permanent of a matrix is known to be #P -complete! (See [358,359].) (The reader is referred
to [124] for a discussion of the concept of #P -completeness and the complexity of enumeration problems.) Thus, the
permanent approach is highly unlikely to ever yield a polynomial procedure for exact counting of 1-factors in simple
bipartite graphs. On the other hand, however, equivalence between the permanent and the number of 1-factors led to
the discovery of a non-trivial lower bound for (G) when G is bipartite and regular.
Theorem 2.20. Let G be a simple k-regular bipartite graph on 2n vertices. Then

n
k
n (G)(k!)n/k .
n
The first inequality in the above theorem is equivalent to the famous van der Waerden Conjecture on permanents which
was formulated in 1926 [360] and proved independently by Falikman [105] and Egoryčev [89,90]. The second inequality
was proved by Brégman [48]. The upper bound is known to be sharp whenever k|n. There has been considerable interest
in improving the lower bound especially for fixed k and large n. Schrijver and Valiant [330,327] conjectured the new
lower bound below and in 1998 Schrijver verified the conjecture.
Theorem 2.21 (Schrijver [329]). If G is a k-regular bipartite graph of order 2n, then
n
(k − 1)k−1
(G) .
k k−2
2.2. (g, f )-factors
Let G be a finite multigraph with loops and let f, g be mappings of V (G) into the non-negative integers.
A (g, f )-factor of G is a spanning subgraph F such that g(v) degF (v) f (v) for all v ∈ V (G).
Note that If f ≡ g ≡ 1, then a (g, f )-factor (i.e., (1, 1)-factor) is just a 1-factor.
The next result, due to Lovász, is known as the (g, f )-factor theorem. Let eG (A, B) denote the number of edges in
graph G joining vertex sets A and B.
Theorem 2.22 (Lovász [250]). Graph G has a (g, f )-factor if and only if
f (D) − g(S) + degG−D (S) − q̂G (D, S, g, f ) 0
for all pairs of disjoint sets D, S ⊆ V (G), where q̂G (D, S, g, f ) denotes the number of components C of G − (D ∪ S)
having g(v) = f (v) for all v ∈ V (C) and eG (V (C), S) + f (V (C)) ≡ 1 (mod 2).
Due to the complicated nature of the (g, f )-factor theorem, it has proven difficult to use in its full generality, but
rather the bulk of results in this direction treat special cases only. For example, the next sample result shows that if one
assumes that g(v) 1, for all v ∈ V (G), the existence criterion for a (g, f )-factor simplifies somewhat.
Theorem 2.23 (Las Vergnas [228]). Let G be a graph and f and g two integer-valued functions defined on V (G) such
that 0 g(x)1 f (x). Then G contains a (g, f )-factor if and only if for every subset X ⊆ V (G), f (X) is at least
equal to the number of components C of G[V − X] such that either C = {x} and g(x) = 1, or |C| is odd and 3 and
g(x) = f (x) = 1 for all x ∈ C.
Several related sufficiency-type theorems can be found in [84]. We state one of them.
Theorem 2.24. Let G be a graph and f and g functions from V (G) to the non-negative integers such that g(v) degG (v),
0 f (v) and g(v) < f (v), for all v ∈ V (G). If
g(x) f (y)
,
degG (x) degG (y)
for every pair of adjacent vertices x and y in G, then G has a (g, f )-factor.
See also [27] for more sufficient conditions for the existence of a (g, f )-factor, [25,141] for simplified existence
theorems for such factors and [183,242,188,243] for the existence of such a factor having additional properties such as
including or excluding prescribed sets of edges.
Once again, let f and g be two functions from V (G) into the positive integers such that g(v) f (v) for all v ∈ V (G)
and suppose that there exists another function h from V (G) to the positive integers such that g(v) h(v) f (v) for
every vertex v ∈ V (G) and h(V (G)) is even. Graph G is said to have all (g, f )-factors if and only if G has an h-factor
for every h such that g(v)h(v)f (v) for all v ∈ V (G).
Theorem 2.25 (Niessen [287]). Let G be a multigraph and let g and f be as above. Then G has all (g, f )-factors if
and only of

∗ −1 if f = g,
g(D) − f (S) + dG−D (S) − qG (D, S, g, f )
0 if f = g,
for all disjoint sets D, S ⊂ V (G), where qG∗ (D, S, g, f ) denotes the number of components C of G − (D ∪ S) such
that there exists a vertex v ∈ V (C) with g(v) < f (v) or eG (V (C), S) + f (V (C)) ≡ 1 (mod 2).
It is apparently unknown whether there is a polynomial algorithm to test if a graph G has all (g, f )-factors.
An exciting alternative approach to (g, f )-factors is provided by the concept of a “fractional” (g, f )-factor. Let G
be a graph without loops in which each edge e has multiplicity ce . As usual, suppose two mappings g and f of V (G)
into the non-negative integers are given with g(v)f (v), for all vertices v ∈ V (G). A vector x = (xe ) with |E(G)| real
components such that 0 xe ce and g(v) degx (v) f (v) for all v is called a fractional (g, f )-factor. Here, degx (v)
is defined to be the sum of the values of all xuv where uv is an edge incident with v.
An important feature of fractional factors is that they can be studied using network flow theory and its accompanying
polynomial algorithms. Moreover, in some cases, fractional (g, f )-factors can be transformed into integral (g, f )-
factors.
Theorem 2.26 (Anstee [26]). Let G, g and f be as above and suppose Gg=f denotes the subgraph of G induced by
the vertices upon which g(v) = f (v). Suppose also that G, g and f satisfy either of the properties (i) or (ii) below.
(i) Gg=f is
bipartite, or
(ii) g = f , v f (v) ≡ 0 (mod 2) and every pair of vertex-disjoint odd cycles are joined by an edge.
Then G has a (g, f )-factor if and only if G has a fractional (g, f )-factor.
The above theorem, in turn, can be used to give a very quick proof of the following result on graphs with the
odd cycle property. (A k-factor is a factor in which all degrees = k. Further results about k-factors will be found in
Section 2.5.)
Theorem 2.27 (Anstee [26]). Let G be a graph with the odd cycle property. Suppose G has a k-factor. Then
(i) for any even integer r k, or
(ii) when |V (G)| is even, for any odd integer r satisfying 1 r < k,
G has an r-factor.
For further information on the connections between network flows and graph factors, as well as fractional (g, f )-
factors, see [110–114,215,244,245,372,378,234,255]. Finally, [148] contains an interesting application of (g, f )-factors
in graphs to statistical data analysis. Fractional matchings have also been studied in [280,46,314,246]. See also [315]
and [253].
2.3. [a, b]-factors
Let a and b be integers such that 1 a b. An [a, b]-factor H of graph G is a factor of G for which a degH (v) b,
for all v ∈ V (G).
Of course, [a, b]-factors are just a special case of (g, f )-factors, but an important one nonetheless.
A sufficient degree condition for the existence of an [a, b]-factor was derived by Li and Mao-cheng [238] and is
presented in the next theorem. This result generalizes previous results of Iida and Nishimura [170] and Nishimura
[293].
Theorem 2.28 (Li and Mao-cheng [238]). Let G be a graph of order n and let a and b be integers such that 1 a < b.
Then if (G)a, n 2a + b + (a 2 − a)/b and
an
max{degG (x), degG (y)} ,
a+b
for any two non-adjacent vertices x and y of G, G has an [a, b]-factor.
Kano [187] obtained the following result involving a criterion having binding number flavor.
Theorem 2.29. Let a and b be integers such that 2 a < b and suppose G is a graph of order at least 6a + b. Define
= b/(a + b − 1). Suppose that for all X ⊆ V (G), N (X) = V (G) if |X| n , and |N (X)| |X|, if |X| < n ,
then G has an [a, b]-factor.
There are a number of results giving sufficient conditions for special graph classes to have [a, b]-factors.
Theorem 2.30 (Kano and Saito [192]). Suppose k, r, s and t are integers such that 0 k r and 1 t. If ks rt, then
an [r, r + s]-graph has a [k, k + t]-factor.
The following gives a sufficient condition for an [a, b]-factor in the line graph of G in terms of the minimum degree
and the independence number of G.
Theorem 2.31 (Nishimura [294]). If G is a and a and b are integers such that 1 a < b, then if (G)((G)/2) + 1,
the line graph L(G) has an [a, b]-factor.
Tokuda [344] and Li [232] have derived a minimum degree criterion and a neighborhood union criterion, respectively,
sufficient for the existence of an [a, b]-factor in K1,n -free graphs.
The next result is very similar in form to Tutte’s 1-factor Theorem. Let i(G) denote the number of isolated vertices
of graph G.
Theorem 2.32 (Las Vergnas [228], Amahashi and Kano [21], Gunther et al. [129]). Let n 2 be an integer. The
following three statements are equivalent:
(i) Graph G has a [1, n]-factor,
(ii) i(G − S)n|S|, for all S ⊆ V (G) and

(iii) |U | n|N(U )|, for all independent subsets U ⊆ V (G).
An important special subclass of [1, n]-factors known as star factors is discussed in Section 3.
The next two results deal with “almost regular” factors. A [k, k + 1]-factor is sometimes called an almost regular
(or semiregular) factor.
Theorem 2.33 (Thomassen [342]). If G is an [r, r + 1]-graph, then G has a [k, k + 1]-factor for all k, 0 k r.
Theorem 2.34 (Kano [186]). Let r 3 be an odd integer and let k be an integer such that 1 k (2r/3) − 1. Then
every r-regular graph has a [k, k + 1]-factor each component of which is regular.
2.4. f-factors
Let G be a multigraph possibly with loops and f, a non-negative, integer-valued function on V (G). Then a spanning
subgraph H of G is called an f-factor of G if degH (v) = f (v), for all v ∈ V (G). (In other words, an f-factor is just an
(f, f )-factor.)
The next result is called Tutte’s f-factor theorem. (See [352] for a proof for locally finite graphs and [353] for a
somewhat shorter proof for the case when the graph is finite.) But first we need some additional notation. If f is a
non-negative integer valued function on V (G), let fˆ be defined by fˆ(v) = degG (v) − f (v). If X, Y ⊆ V (G), let
∇(X, Y ) denote the set of edges joining X and Y.
Theorem 2.35. Graph G has an f-factor if and only if for every two disjoint subsets X and Y of V (G), the number of
components K of G − X − Y for which f (V (K)) + |∇(X, Y )| is odd, does not exceed f (X) + fˆ(Y ) − |∇(X, Y )|.
It is an interesting fact that although Lovász [250] generalized the f-factor theorem of Tutte via his (g, f )-factor
theorem, it was shown later by Tutte [356] that, in fact, conversely, the (g, f )-factor theorem can be derived from the
f-factor theorem. Thus, in a sense the two results are equivalent.
Recall that by the 1-factor Theorem of Tutte, we know that if a graph G has no 1-factor, then there must exist a set
S ⊆ V (G) such that co (G − S) > |S|. Such a set S is called a 1-barrier or antifactor set. So Tutte’s 1-factor theorem
could be restated to say that a graph has a 1-factor if and only if it has no 1-barrier. An alternate form of the f-factor
theorem, similar in form to this restatement of the 1-factor Theorem, was derived by Tutte [352,353, see also 355],
using the concept of an f-barrier, where an f-barrier is a generalization of the idea of a 1-barrier. We do not treat the
details here but instead simply state this result.
Theorem 2.36 (Tutte [352,353]). A graph G has an f-factor if and only if it does not have an f-barrier.
Fulkerson et al. [119] also found a necessary and sufficient condition for a graph with the odd cycle property to have
an f-factor, and used integer programming to prove their result. Mahmoodian [256] later showed that this result was a
corollary to Tutte’s f-factor theorem. See also [226].
It is important to know that the f-factor problem can, in a sense, be reduced to the 1-factor problem and this reduction
was known to Tutte already in 1954 [353]. More particularly, there exists a procedure for reducing the f-factor problem
on a graph G to the 1-factor problem on a larger graph G . (We will not go into the details here, but instead refer the
interested reader to Chapter 10 of [253] or Chapter 2 of [36].)
In many cases, by virtue of the next theorem, due to Kotani, one can reduce the question of the existence of an
f-factor in a graph G to the same question applied to a collection of its induced subgraphs of fixed order.
Theorem 2.37 (Kotani [220]). Let G be a connected graph and let p be an integer such that 0 < p < |V (G)|. Let f
be an integer-valued function on V (G) such that 2 f (v) degG (v) for
all v ∈ V (G). If every connected induced
subgraph of order p of G has an f-factor, then G has an f-factor, or else v f (v) is odd.
Sufficient conditions for an f-factor in terms of (G), of the binding number of G and of the connectivity and
independence number of G, respectively, are provided by the next three results.
Theorem 2.38 (Katerinis and Tsikopoulos [205]). Let G be a graph and a b, two positive integers. Suppose further
that
b
(i) (G) |V (G)|, and
a+b
a+b
(ii) |V (G)| > (b + a − 3).
a

Then if f is a function from V (G) to {a, a + 1, . . . , b} such that v f (v) is even, G has an f-factor.
Theorem 2.39 (Kano and Tokushige [193]). Let G be a connected graph of order n, let a
and b be two integers such
that 1 a b and 2 b, and let f : V (G) → {a, a + 1, . . . , b} be a function such that v f (v) is even. Then if the
binding number of G is greater than (a + b − 1)(n − 1)/(an − (a + b) + 3) and n (a + b)2 /a, G has an f-factor.
Theorem 2.40 (Katerinis and Tsikopoulos [206]). Let G be a graph, a and b two positive integers with a b and
2 b 3 and suppose that
2(b − 1)
(i) (G) (G) and
a
(ii) |V (G)| 8.
If f is a function from V (G) to the positive integers such that

(iii) x∈V (G) f (x) is even and

(iv) a f (x)b for every x ∈ V (G),
then G has an f-factor.
In the special case when G has an f-factor such that f (v) is odd, for all v ∈ V (G), G is said to have an odd f-factor.
Amahashi has found a simple Tutte-like criterion for a graph to have an odd f-factor.
Theorem 2.41 (Amahashi [20]). Let G be a graph and n a positive integer. Then G has a {1, 3, . . . , 2n − 1}-factor if
and only if
co (G − S) (2n − 1)|S|,
for every S ⊆ V (G).
See also [71,349,190]. In [191] one finds a polynomial algorithm to find an odd f-factor which is in a sense optimal
in terms of its deficiency at each vertex.
2.5. k-factors
An f-factor for which f (v) = k, for all v ∈ V (G), is called a k-factor. Petersen, by virtue of a second theorem in his
1891 paper, was present at the creation of the study of k-factors as well.
Theorem 2.42 (Petersen [304]). A graph G has a factorization into 2-factors if and only if it is regular of even degree.
The analogous result for regular graphs of odd degree did not appear until almost 50 years later and is due to Bäbler.
Theorem 2.43 (Bäbler [29]). Every 2-edge-connected (2k + 1)-regular multigraph contains a 2-factor.
A thorough survey tracing the descendants of Petersen’s factorization results for regular graphs may be found in
Volkmann [362].
There is now an extensive literature on the subject of sufficient conditions for the existence of a k-factor. We present
only a sampling.
Chvátal [61], who invented the graph parameter called toughness, conjectured the following result which was proved
in [97].
Theorem 2.44. If tough (G) k, then G has an k-factor.
(Katerinis [203] later generalized this result to one about f-factors.)

A sufficient condition for an k-factor, in terms of (G) and (G), is found in the next result. This condition is
reminiscent of the well-known Chvátal–Erdős condition for the existence of a Hamilton cycle.
Theorem 2.45 (Nishimura [290,291]). Let G be a graph and k, an even non-negative integer. If
(G) max{k(k + 2)/2, (k + 2)(G)/4},
then G has an k-factor.
(See also [201,286].)

The condition involving degree sums given in the next theorem is often called an Ore condition after Oystein Ore
who first introduced a condition of this type and showed it to be sufficient for the existence of a Hamilton cycle. In
[207,79,345,365,229], one finds theorems with hypotheses involving the binding number or conditions suggesting the
binding number. We shall be content to state the following result which involves both an hypothesis suggesting the
binding number and a second hypothesis which is an Ore condition.
Theorem 2.46 (Lenkewitz and Volkmann [229]). Let k 2 be an integer and G a graph of order n with n 4k − 6 and
(G)k. If k is odd, then n is even and G is connected. Let G satisfy
1
|N (X)| (|X| + (k − 1)n − 1),
2k − 1
for every independent subset X of V (G) with |X|2k, and
2k − 2 4k − 5
deg(u) + deg(v) n+ .
2k − 1 2k − 1
Then G has a k-factor.
Again, following analogous results for the existence of Hamilton cycles, the next result gives a sufficient condition
for the existence of a k-factor in terms of what is called a neighborhood union condition.
Theorem 2.47 (Iida and Nishimura [171]). Let k 2 be an integer and let G be a connected graph of order n,
minimum degree at least k and suppose kn is even. Suppose further that n 9k − 1 − 4 2(k − 1)2 + 2. Then if
|NG (u) ∪ NG (v)| (1/2)(n + k − 2) for each pair of non-adjacent vertices u and v, G has a k-factor.
Matsuda [263] later extended this result by giving a neighborhood union condition sufficient for the existence of an
[a, b]-factor and his result was, in turn, further generalized by Li. (See [233].)
Yet another kind of bound involving the degrees of non-adjacent vertices is given next.
Theorem 2.48 (Nishimura [293]). Let G be a connected graph of order n and let k be an integer 3 such that kn is
even, n4k − 3 and (G) k. Then if max{d(u), d(v)}n/2, for all pairs of non-adjacent vertices u and v, G has a
k-factor.
We next present a minimum degree condition sufficient to guarantee a k-factor in a claw-free graph. (See also
[107].)
Theorem 2.49 (Egawa and Ota [86]). If G is a connected claw-free graph with (G) (9k + 12)/8 and if k|V (G)|
is even, then G has a k-factor.
The following result gives a condition on the minimum degree in claw-free graphs sufficient to yield a 2-factor with
a bounded number of cyclic components.
Theorem 2.50 (Faudree et al. [106]). If G is claw-free with (G)4, then G has a 2-factor with at most [6n/((G) +
2)] − 1 components. Moreover, there is an O(n3 ) algorithm to construct such a 2-factor.
(See also [323,47] and [57].)

A well-known conjecture about 2-factors is known as El-Zahár’s Conjecture.
Conjecture 2.51 (El-Zahár [95]). If G is a graph with n = n1 + · · · + nk vertices and (G) n1 /2 + · · · + nk /2,
then G has a 2-factor in which the cycles have lengths n1 , . . . , nk , respectively.
El-Zahár himself proved the conjecture true in the case k = 2 and Corrádi and Hajnal [69] proved it true when each
ni = 3. Further partial results can be found in [179]. We understand that Abbasi [1] has settled the conjecture for
n = |V (G)| sufficiently large, but to the best of our knowledge, no proof has yet been published.
Kundu was able to generalize his 1-factor theorem about degree sequences to the k-factor case.
Theorem 2.52 (Kundu [225]). If k is a positive integer and the sequences d1 , . . . , dn and d1 − k, . . . , dn − k are both
graphical, then d1 , . . . , dn can be realized by a graph G which contains a k-factor.
Kleitman and Wang [214] give an alternate proof of Kundu’s result and also give a polynomial algorithm for
constructing such a graph G containing a k-factor.
The next three results yield conditions on vertex-deleted subgraphs sufficient to guarantee the existence of a k-factor
in the parent graph.
Theorem 2.53 (Egawa et al. [81]). Let G be a connected graph and p be an integer such that 0 < p < |V (G)|. Suppose
k|V (G)| is even and G − V (P ) has a k-factor for each connected induced subgraph P of order p. Then G has a k-factor.
Theorem 2.54 (Saito [324]). Suppose G is a graph with a 1-factor F and order at least four and let k be a positive
integer. Then if G − {u, v} has a k-factor for each edge uv ∈ F , G itself has a k-factor.
(See [101] for a generalization of the above result.)

A graph G is hypohamiltonian (respectively, hypotraceable) if G does not have a Hamilton cycle (respectively, path),
but G − v does, for all v ∈ V (G).
Theorem 2.55 (Katerinis [199]). If G is either hypohamiltonian or hypotraceable, then G has a 2-factor.
A sufficient condition for a k-factor in the line graph is given next.
Theorem 2.56 (Nishimura [292]). If k 2 is an integer and G is a connected graph with k|E(G)| even and if
(L(G))(9k + 12)/8, then L(G) has a k-factor.
A sample result on the existence of k-factors in bipartite graphs is the following.
Theorem 2.57 (Katerinis [204]). Let G be a bipartite graph with bipartition V (G) = X ∪ Y and k be a positive integer.
Then if:
(i) |X| = |Y |,
(ii) (G)|X|/2√ k, and
(iii) |X|4k − 4 k + 1, when |X| is odd and |X|4k − 2, when |X| is even, then G has a k-factor.
Hall-type conditions sufficient for a bipartite graph to have a 2-factor (respectively, k-factor) may be found in [202]
(respectively, [100]). Conditions for the existence of k-factors in multipartite graphs have been obtained by Hoffmann
[160,161] and by Hoffmann and Rodger [159].
Suppose G is r-regular and has edge-connectivity . If G is a multigraph, all values of k for which G is guaranteed
to have a k-factor are known [42]. Similarly, all such k are known when G is simple [288].
Katerinis [200] has obtained the following “interpolation” theorem about k factors.
Theorem 2.58. Let m, , n be three odd integers such that m < < n. Then if graph G has an m-factor and an n-factor,
it also has an -factor.
A recent interesting generalization of the above result may be found in [28].

Bermond and Las Vergnas [32] showed that in a graph which is not regular, but is “sufficiently close” to being regular,
one can guarantee the existence of odd and even k-factors.
In a very recent paper, Hoffmann and Volkmann [165] prove the following result about k-factors in graphs with small
diameter.
Theorem 2.59. A connected d-regular graph with d 2 and diameter 3, has every k-factor for k|V (G)| even.
Hendry [149] initiated the study of graphs with unique k-factors and his conjecture on the maximum number of edges
that such a graph may have was proved by Johann [177,178]. Results on the structure of a bipartite graph possessing a
unique k-factor may be found in [163,164].
Jackson and Whitty proved an interesting result about degrees in the presence of a unique f-factor.
Theorem 2.60 (Jackson and Whitty [173]). If G is a 2-edge-connected graph with a unique f-factor F, then some
vertex has the same degree in F as in G.
In [120,121], the authors show that the O(|E|log4 |V |) algorithm for unique 1-factors can be extended to finding a
unique f-factor, if one exists. The running time of the extended algorithm remains the same as that for the 1-factor case.
2.6. Connected factors
It is also of interest to investigate when one can be assured of the existence of a connected factor. For example, a
Hamilton cycle is just a connected 2-factor.
Theorem 2.61 (Kano [189]). Let k be a positive integer and let G be a connected graph of order n and minimum degree
greater than k where kn is even and n 4k−5. If for each pair of non-adjacent vertices u and v of G, deg(u)+deg(v) n,
then G has both a Hamilton cycle C and a k-factor F. Hence G has a connected [k, k + 2]-factor.
Matsuda [266,267] has extended the above result to the cases of [a, b]-factors (and k-factors) containing a given
Hamilton cycle.
Kano conjectured that the hypotheses of the above theorem were sufficient to guarantee the existence of a [k, k + 1]-
factor and this follows from the next result.
Theorem 2.62 (Li and Mao-cheng [237]). Let G be a connected graph of order n and let f and g be two functions from
V (G) to the positive integers which satisfy 2 g(v)f (v) for each vertex v ∈ V (G). Suppose G has an (g, f )-factor
F and put = min{g(v)|v ∈ V (G)}. Suppose that among any three independent vertices of G there are (at least) two
vertices with degree sum at least n − . Then G has a matching M such that M and F are edge-disjoint and M ∪ F is
a connected (g, f + 1)-factor.
(See also [258,259].)
Theorem 2.63 (Li and Liu [230]). If G is a 2-connected claw-free graph, then G has a connected [2, 3]-factor.
Theorem 2.64 (Li et al. [231]). If G is a 2-connected claw-free graph containing a k-factor where k 2, then G
contains a connected [k, k + 1]-factor.
Theorem 2.65 (Xu et al. [368]). Let n3 be an integer and let G be a K1,n -free graph. Suppose f and g are positive
integer-valued functions defined on V (G) such that g(v) f (v), for all v ∈ V (G). Then if G has a (g, f )-factor, G
has a connected (g, f + n − 1)-factor.
Theorem 2.66 (Kouider and Mahéo [223]). Let G be a connected graph of order n and minimum degree . Let a and
b be two integers such that 2a b. Suppose further that n ((a + b)(a + b − 1))/b and (G)n/(1 + b/a ), then
G has a connected [a, b]-factor.
(See also [93] and [281].)

In [235] and [236] the authors derive a degree sum condition for graphs containing a Hamiltonian cycle H which is
sufficient to guarantee the existence of a [k, k + 1]-factor containing H. (See also [265].)
Tutte [354] discovered a simple criterion for a graph to decompose into a prescribed number of connected factors.
Theorem 2.67. A graph G decomposes into n connected factors if and only if for all 0 deleting any set of edges
from G leaves a graph with at most 1 + /n components.
We will not go further in the direction of connected factors, but refer the reader to a survey on the subject of connected
graph factors (including spanning trees) by Kouider and Vestergaard [224].
3. Component factors
In a sense, the results of Section 2.6 above provide a nice transition to this section. There the issue was the existence
of a type of degree factor which had only one component, namely a degree factor which was connected. In this section
we address problems concerning factors each component of which is described by properties other a degree bound.
The next definition will serve as a good beginning point.
Let {G1 , G2 , . . . , Gk } be an arbitrary set of k graphs. Then graph G is said to have a {G1 , G2 , . . . , Gk }-factor if G
has a factor each component of which isomorphic to some member of {G1 , G2 , . . . , Gk }. (Here we wish to make it
clear that the components of the factor sought may be isomorphic to different members of {G1 , G2 , . . . , Gk }.)
For example, suppose it is required that each component of the factor be a path. Such a factor is called a path factor.
Recall that Pi denotes a path having exactly i vertices. It is of interest to note that by Theorem 2.32, a graph G has a
path factor if and only if i(G − S) 2|S|, since the following three statements are clearly equivalent:
(i) G has a path factor,

(ii) G has a {P2 , P3 }-factor and
(iii) G has a {K1,1 , K1,2 }-factor.
Kaneko [180] proved part (a) of the following. Part (b) was obtained in [209].
Theorem 3.1. (a) Every 3-regular graph has a {P3 , P4 , P5 }-factor.

(b) Every 2-connected 3-regular graph has a {P3 , P4 }-factor.
An interesting conjecture along this line, due to Akiyama and Kano [11,12], remains open.
Conjecture 3.2. Every 3-connected 3-regular graph of order divisible by three has a P3 -factor.
The next result gives a sufficient condition for a graph to have a P3 -factor in the case in which it is claw-free.
Theorem 3.3 (Kaneko et al. [181]). Let G be a claw-free graph with |V (G)| ≡ 0 mod 3 and having at most two
endblocks. Then G has a P3 -factor.
A bit more generally, one can ask when there exists a path factor each component of which has a prescribed minimum
length. For example, Kaneko [180] has found a necessary and sufficient condition for a graph to have a factor each
component of which is a path on at least three vertices. This result, which involves a Tutte-like condition, is perhaps
the first characterization of graphs which have a path factor not including K2 = P2 .
A graph G is said to be factor-critical if G − v has a perfect matching for every vertex v ∈ V (G). Let G be a factor-
critical graph with at least three vertices and suppose V (G) = {v1 , v2 , . . . , vn }. Add n new vertices {w1 , w2 , . . . , wn }
to G together with edges vi wi , for 1 i n. The resulting graph H on 2n vertices is called a sun. Let cs (G) denote the
number of components of G which are sun graphs. Then Kaneko’s result can be stated as follows.
Theorem 3.4. A graph G has a path factor in which every component path has length at least two if and only if
cs (G − S)2|S|, for every subset S ⊆ V (G).
For claw-free graphs, one has the next result.
Theorem 3.5 (Ando et al. [23]). Let d be a non-negative integer and let G be a claw-free graph with (G) d. Then
G has a path factor in which all paths have at least d + 1 vertices.
An Fc -factor is a spanning subgraph in which each component is a single edge or an odd cycle. (Note that the
terminology “Fc -factor” is our own. These factors were originally called “F-factors”, but the terms “F-factor” and
“F-factorization problem” have subsequently come to mean something else and hence we will reserve them for a
different use later on in this paper.) The next result involving Fc -factors can be viewed as a generalization of Hall’s
Theorem on perfect matchings to the non-bipartite case.
Theorem 3.6 (Steinparz [338]). A graph G has an Fc -factor if and only if |N (S)| |S|, for every S ⊆ V (G).
Another type of component factor which has been studied is the “star”. A star is a subgraph isomorphic to the
complete bipartite graph K1,n , for any n 1. Let S denote the family of all stars having at least one edge and
let Sn denote the family of all stars having at least one and at most n edges. Las Vergnas, Amahashi and Kano,
Egawa, Kano and Kelmans, Saito and Watanabe, Gunther, Hartnell and Rall, Chen, Egawa and Kano, as well as
Hell and Kirkpatrick, among others, have studied so-called star factors, that is, factors each component of which is a
star.
The first statement in the following theorem involves a criterion similar in form to Tutte’s 1-factor criterion. Here
i(G) denotes the number of isolated vertices of graph G.
Theorem 3.7 (Las Vergnas [228], Amahashi and Kano [21], Gunther et al. [129]; see also Hell and Kirkpatrick
[145]). Let n be an integer greater than or equal to 2. Then the following statements are equivalent:
(1) G has an Sn -factor,
(2) i(G − S)n|S| for every S ⊆ V (G),
(3) |N (U )| (1/n)|U | for every independent set U ⊆ V (G).
(See also Section 2.3 above.)

Yu [373] has studied the “barriers” involved, i.e., the sets S which fail to satisfy condition (2) above. He has also
shown [374] that every regular graph has the property that every edge lies in some S-factor. See also [55] for a related
result for not necessarily regular graphs and [54] for an analogous result for the situation when the degrees of the stars
are bounded above by a given function on the vertices.
Let us now call a star factor of a graph G strong if each of the stars is an induced subgraph of G.
Theorem 3.8 (Kelmans [210], Saito and Watanabe [325]). A connected graph G has a strong S-factor if and only if
G is not an odd-cactus.
(A graph is a cactus (or clique tree) if it is connected and each of its blocks is complete and a cactus (clique tree) is
odd if each of its blocks has odd order.)
Theorem 3.9 (Egawa et al. [85]). Let n 2 be an integer. Then a graph G has a strong Sn -factor if and only if
coc (G − S)n|S| for all subsets S ⊆ V (G), where coc (G − S) denotes the number of odd cactus components
of G − S.
Yu has studied graphs with a unique Sn -factor and in addition, has proved the following result.
Theorem 3.10 (Yu [375]). Let r 4 be an integer and let G be a connected r-regular graph of order n which is not
isomorphic to Kr,r . Then G has at least n star factors each of which is either a proper Sr -factor or a proper Sr−1 -factor.
(Here a Sr -factor is proper if it has at least one component isomorphic to K1,r ).

In the special case of S4 -factors in which every component is isomorphic to a K1,3 , Egawa and Ota proved the
following.
Theorem 3.11 (Egawa and Ota [88]). Let k be a positive integer. Then if G is a graph of order 4k with minimum degree
at least 2k, then G contains a S4 -factor each component of which is isomorphic to a K1,3 , unless G is isomorphic to
K2k,2k , with k being odd.
For an extension to the case where each component of the factor is a K1,t , see [118].
Another interesting special case is the following. Let K4 − e denote the complete graph K4 with one edge e removed.
Theorem 3.12 (Kawarabayashi [208]). Let G be a graph of order 4k with (G) 5k/2. Then G contains a (K4 − e)-
factor.
The next result specifies the number of components of the factor sought as well as the maximum degrees within the
components.
Theorem 3.13 (Lovász [249]). Let G be a graph with maximum degree and let be a non-negative integer. Sup-
pose further that k1 + k2 + · · · + k = − + 1, where each ki is a non-negative integer. Then V (G) can be
partitioned into disjoint subsets Vi such that each vertex of Gi = G[Vi ] is joined to at most ki other vertices
of Gi , for i = 1, . . . , .
The above result of Lovász has been used to derive best known error bounds in certain branches of coding
theory [70].
The next variation, proved independently by Györi [131] and Lovász [252], answered a conjecture of Frank con-
cerning the partitioning the vertex set of the graph into vertex-disjoint subgraphs each of which contains a prescribed
vertex.
Theorem 3.14 (Lovász [252], Györi [131]). Let G be a k-connected graph and suppose v1 , . . . , vk are k distinct
vertices of G. Suppose further that |V (G)| = n = n1 + · · · + nk is a partition of |V (G)| = n into k positive
parts.
Then V (G) can be partitioned into k disjoint subsets Vi such that vi ∈ Vi , |Vi | = ni and G[Vi ] is connected for every
1 i n.
In the next result a minimum degree condition replaces the connectivity condition. (See also [82].)
Theorem 3.15 (Enomoto and Matsunaga [99]). Let G be a graph of order n and suppose n = a1 + · · · + ak is a
partition of n where each ai 2. Suppose (G) 3k − 2. Then given any k distinct vertices v1 , . . . , vk ∈ V (G), V (G)
can be partitioned as V (G) = A1 ∪ · · · ∪ Ak such that |Ai | = ai , vi ∈ Ai and (G[Ai ]) > 0, for all 1 i k.
(See [172] and [80] for recent work on closely related problems.)
Certain connectivity or minimum degree conditions on the parent graph may suffice to guarantee a partition the
component subgraphs of which have either prescribed connectivity or minimum degree.
Theorem 3.16. (a) (Thomassen [343]) For each pair of positive integers (s, t), there exist positive integers f (s, t)
and g(s, t) such that each graph G with (G) f (s, t) (respectively, (G)g(s, t)) admits a partition of its vertex set
V (G) = S ∪ T such that the induced subgraphs G[S] and G[T ] have connectivity (respectively, minimum degree) at
least s and t, respectively.
(b) (Hajnal [133]) Moreover, if s 3 and t 2, then f (s, t)4s + 4t − 13 and if s 4, then g(s, t) t + 2s − 3.
(The reader is also referred to [96,98].)

Finally, Nishimura [295] has found that one can determine the existence in a graph G of a factor each component of
which is isomorphic to a second graph H by checking certain subgraphs of G for such a factor.
Theorem 3.17. Let G and K be connected graphs such that |V (G)| = n|V (K)|, for some n 2, and let p be a fixed
integer satisfying 1 < p < n. Then if G − A has a K-factor for every connected subgraph A with |V (A)| = p|V (K)|,
it follows that G also has a K-factor.
4. Factors in random graphs
There are several popular models of so-called random graphs. We will be content to refer to only one of these.
Let 1, . . . , n be a labelling of the vertices and let {eij }, 1 i < j n, be an array of independent random variables,
where each eij assumes the value 1 with probability p and 0 with probability 1 − p. This array determines a random
graph on {1, . . . , n} where each (ij ) is an edge if and only if eij = 1. This probability space (or random graph) is
denoted by Gn,p .
An event E concerning a graph G ∈ Gn,p is said to hold asymptotically almost surely (or a.a.s.), if limn→∞ Prob E=1.
Theorem 4.1 (Erdős and Rényi [104]). Let n be even and p = (1/n)(log n + w(n)), with limn→∞ w(n) = ∞. Then
G ∈ Gn,p has a 1-factor a.a.s.
Theorem 4.2 (Shamir and Upfal [331]). Let p = (1/n)(log n + (r − 1) log log n +
w(n)), with r 1 and suppose
limn→∞ w(n)=∞. Suppose further that f is a mapping from V (G) into {1, . . . , r} with ri=1 f (xi ) even. Then G ∈ Gn,p
has an f-factor a.a.s.
For excellent treatments of random graphs and their factors, the reader is referred to [37–41,64,115,174,175,195,196,
276–278,319,322,331,332].
5. Graph factorization
Recall that a factorization of a graph G normally refers to a partition of the edge set of G into factors.
5.1. 1-factorizations
We begin with the widely studied 1-factorization Conjecture. (See [58,363, Ch. 19].)
Conjecture 5.1. Let G be a simple graph of even order n. If G is regular with (G)n/2, then (G) = (G); that is,
G is Class 1 (i.e., G has a 1-factorization).
To date the best result toward this conjecture is the following due to Chetwynd and Hilton [59] and, independently,
to Niessen and Volkmann [289].
√
Theorem 5.2. If one replaces n/2 by ( 7 − 1)n/2, the above conjecture becomes true.
See also [51].

The following, due to Plantholt and Tipnis, may be viewed as an extension of the Chetwynd–Hilton–Niessen–Volkmann
result to the multigraph case. (See also [308].)
Theorem 5.3 (Planthold and Tipnis [307]). Let G be a regular multigraph of even order n and multiplicity (G) r.
Then if (G)r(5n/6 + 1), (G) = (G).
Evidence in favor of the truth of the 1-factorization Conjecture for “large” graphs is given by the following (See
[302] and Häggkvist (unpublished)).
Theorem 5.4. Given > 0, there is a number N = N () such that if G is a -regular simple graph of even order greater
than N, and ( 21 + )|V (G)|, then G has a 1-factorization.
Another approach to the conjecture is represented by the following result.
Theorem 5.5 (Zhang and Zhu [376]). Every k-regular graph of order 2n contains at least k/2 edge-disjoint
1-factors, if k n.
For general references to edge coloring see [109,108,154,158,176]. (A more general conjecture, called the overfull
conjecture and due also to Chetwynd and Hilton [58], would imply the 1-factorization Conjecture. See also [153,156].)
5.2. [a, b]-factorizations
Next we turn to an example of a more general type of factorization, called [a, b]-factorization. A graph G is an [a, b]-
graph if a deg(v)b, for every vertex v ∈ V (G). A graph then has an [a, b]-factorization if it has a factorization
into an edge-disjoint union of [a, b]-graphs each of which spans G.
Theorem 5.6 (Kano [184]). Suppose a and b are integers such that 0 a b.
(i) A graph G has a [2a, 2b]-factorization if and only if G is a [2am, 2bm]-graph for some integer m, and
(ii) every [8m + 2k, 10m + 2k]-graph has a [1, 2] factorization.
(See also [257] and [13].)

Kano [185] has also obtained the next result on [a, b]-factorization which involves the “odd cycle property” introduced
in Section 2.1.
Theorem 5.7. Let a and b be integers with 0 a b and let G be a graph with the odd cycle property. Then G is
[a, b]-factorizable if and only if G is an [an, bn]-graph for some positive integer n.
We next present a sample result on (g, f )-factorization; that is, a representation of E(G) as the edge-disjoint union
of (g, f )-factors. (See [369,370] for other such results.)
Theorem 5.8 (Yan et al. [371]). Let G be a multigraph and let g and f be two functions mapping V (G) into the
non-negative integers. Let m be a positive integer and an integer with 0 3 and ≡ m(mod 4). Then if G is an
(m + 2m/4 + , mf − 2m/4 − ) graph, G has a (g, f )-factorization.
Era [102] and Egawa [78] seem to have been the first to consider factorizations in which the factors are “almost
regular”. Two of their results appear below combined into one corollary to the following theorem due, very recently,
to Hilton [155].
Theorem 5.9. Let G be a simple d-regular graph and suppose r 2. Then
(i) G has an ([r, r + 1]-factorization with exactly x [r, r + 1]-factors if

(1-a) d/(r + 1) < x < d/r or
(1-b) if r is odd and x = d/(r + 1) or
(1-c) if r is even and x = d/r.
(ii) If r is even and (r + 1)|d, then there are d-regular simple graphs which are, and d-regular simple graphs which
are not, [r, r + 1]-factorizable into x = d/(r + 1) [r, r + 1]-factors; if r is odd and r|d, then there are d-regular
simple graphs which are, and d-regular simple graphs which are not [r, r + 1]-factorizable into x = (d/r)
[r, r + 1]-factors.
(iii) If x ∈/ [d/(r + 1), d/r], then no d-regular simple graph is [r, r + 1]-factorizable into x [r, r + 1]-factors.
Corollary 5.10 (Era [102], Egawa [78]). Let k 2 be an integer. Then:
(i) every r-regular graph G with r 4k 2 has a [2k, 2k + 1]-factorization and
(ii) every (k 2 − 4k + 2)-regular graph G has a [2k − 1, 2k]-factorization.
Lonc [248] has shown that if S− is a family of stars from which the one and two edge stars are deleted, it is
NP-complete to decide whether a bipartite graph admits an S− factorization.
Some observations about connections between the 1-factorization problem and combinatorial designs may be found
in [138]. The subjects of 1-factorizations of graphs in general, or complete graphs in particular, are enormous topics
unto themselves and quickly lead one into the discipline of combinatorial design theory. We will not treat these topics
further, but instead direct the interested reader to several excellent surveys [333,273,239,274] and the more recent
encyclopedic volume of Wallis [363].
5.3. Linear arboricity
A different type of edge partition problem is represented by the concept of linear arboricity. The linear arboricity
a(G), of graph G is the minimum number of paths which together partition E(G). (See [136]. An alternate name for
this parameter is path-chromatic index. See [151].)
Akiyama, Exoo and Harary showed the following.
Theorem 5.11 (Akiyama et al. [10]). If G is any graph, a(G) 3/2/2.
There are two interesting conjectures on linear arboricity in existence. The first one was formulated in [9], the second
in [151] and both remain unsettled.
Theorem 5.12 (Linear arboricity conjecture I (LAC-I)). The linear arboricity of every d-regular graph is (d + 1)/2.
Theorem 5.13 (Linear arboricity conjecture II (LAC-II)). The linear arboricity of any graph G is bounded above by
((G) + 1)/2.
McDiarmid and Reed [271] proved that for every d, almost all n-vertex, d-regular graphs satisfy LAC-I and later
[272] showed that almost all graphs satisfy LAC-II. Guldan [128] proved LAC-I when the degree of regularity is large
with respect to the order of the graph. Truszczynski [350] proved that if LAC-I holds for each of two regular graphs
G and H, then it holds for their Cartesian product G × H . Wu [367] proved LAC-II for all planar graphs with = 7.
Alon [14] proved LAC-II for every graph with even (respectively, odd) maximum and girth at least 50 (respectively,
100). In the same paper, Alon also proved that LAC-II is asymptotically correct in the sense that the linear arboricity is
bounded above by (1/2 + ) for every graph G with sufficiently large . Péroche [303] showed that it is NP-complete
to determine whether it is possible to partition the edge set E(G) into k paths when (G) = 2k.
There has also been work done on the related parameter called k-linear arboricity, denoted a(G), which is defined
to be the minimum number of paths, each of length no more than k, which partition E(G). See [132,19]. Note that
1 (G) is just the edge chromatic number of graph G.
5.4. Factorizations of complete graphs
The problem of partitioning the edge set of a complete graph Kn into disjoint factors has received widespread
attention. The existence of such a factorization has been studied for many different prescribed properties of the factors
involved.
One interesting example arises when one limits the diameter of the factors. The first research upon this problem
dates from Bosák et al. [45]. For k 2, let f (k) denote the smallest positive integer such that the complete graph of
order f (k) admits a factorization into k factors, each having diameter 2. Znam [379] proved that if k is sufficiently
large, then f (k) = 6k. Bosák [43] had shown earlier that 6k − 52 f (k)6k for all values of k 2. Scattered results
involving bounds for small values of k exist (e.g., see [260]), but a complete determination of f (k) remains unsettled.
The variant of the above problem obtained when one prescribes the radii of the factors, rather than the diameters,
seems to have been first proposed by Rosa. See [301,346] for results on this variation and when both the diameter and
radius of the factor is prescribed, see [285,347,348]. If it is demanded that the factors of given diameter must also be
isomorphic, see [222,150]. If the number of factors of given diameter is prescribed, see [45,299,300,169,117].
Several interesting new problems concerned with factoring the complete graph into factors all of which are r-regular
are posed in [157] and the authors make some progress in several special cases.
Martin [261,262] has studied the factorization of the complete bipartite graph Km,n into factors of type Kp,q .
6. Factor algorithms and complexity
Throughout this section, let n = |V (G)| and m = |E(G)|. The first polynomial algorithm for matching in an arbitrary
graph was formulated by Edmonds [76] and has come to be known as the blossom algorithm. Its running time is O(n4 ).
The fastest
√ algorithm to date for maximum matching in a general (i.e., not necessarily bipartite) graph has complexity
O(m n) and is due to Micali and Vazirani [275]. (Curiously, a proof of correctness of this algorithm was not published
until fourteen years later! (See [361]. See also [305].)) Since the Micali–Vazirani algorithm was introduced, two other
matching algorithms [122,35] having the same complexity as Micali–Vazirani have been produced.
Faster algorithms exist, however, in certain special cases. If the graph is 3-regular and has no cutedge, then by the
classical result of Petersen [304], the graph must have a 1-factor. For this case, an O(n log4 n) algorithm is given in
[34] for finding a 1-factor. If, in addition, the graph is planar, then an O(n) algorithm is also given.
The Gabow, Kaplan and Tarjan algorithm mentioned above [121] can be modified to test whether a graph has a
unique f-factor and find it, if it exists, and to check whether a given f-factor is unique, all in polynomial time.
Anstee [24] gave algorithmic proofs of both the (g, f )-factor theorem and the f-factor theorem and his algorithms
either return one of the factors in question or show that none exists, all in O(n3 ) time. Note that this complexity bound
is independent of the functions g and f.
Fc -factors (introduced in Section 3) can be determined in polynomial time.
Theorem 6.1 (Mühlbacher [279], Hell and Kirkpatrick [143]). There is a polynomial algorithm for finding an
Fc -factor or showing that none exists.
A polynomial algorithm for finding a 2-factor, if one exists, was first found by Edmonds and Johnson [77]. If one
additionally demands that the 2-factor be triangle-free, the problem remains polynomially solvable. (See [67,139].)
For graphs in general, if one demands that the forbidden cycle lengths form a non-empty subset of {5, 6, . . .}, the
problem has been shown to be NP-complete [147]. If one forbids only C3 , C4 and C5 , the problem is again NP-complete
[Papadimitriou; see 67]. The complexity in the two remaining cases, namely where only 4-cycles are forbidden or where
only triangles and 4-cycles are forbidden, remains unresolved. For the intermediate case when the graph is bipartite
and it is required to find a 2-factor which has no 4-cycle component, there is a polynomial algorithm [140]. (For an
extension of Hartvigsen’s result to f-factors, see [211].)
The problem of deciding whether or not a graph has a Hamilton cycle was one of first decision problems proved to be
NP-complete by Karp [197,198]. The problem remains NP-complete, even if the graphs are restricted to be 3-regular
and planar [125] or 4- or 5-regular and planar [306]. These results would seem to indicate that few connected factor
problems are likely to be polynomially solvable.
Let G be an arbitrary graph. A G-factor of a graph H is a set {G1 , . . . , Gd } of subgraphs of H such that each Gi is
isomorphic to G and the sets V (Gi ) collectively partition V (G).
Let F ACT (G) denote the recognition problem:
INSTANCE: A graph H.
QUESTION: Does H admit a G-factor?
The answer to F ACT (K1 ) is (trivially) always “yes” and so F ACT (K1 ) ∈ P . Problem F ACT (K2 ) is just the
question of the existence of a perfect matching in H and hence also lies in P. More generally, if G consists of a disjoint
union of copies of K1 and K2 , F ACT (G) belongs to P. Interestingly, however, we have the next result [213]. (See
[212] for a nice application to exam scheduling and see also [144].)
Theorem 6.2. If some component of G has more than two vertices, then F ACT (G) is NP-complete.
A set S (respectively, Sn ) of stars is said to be sequential if S = {K1,1 , K1,2 , K1,3 , . . .} (respectively Sn =

{K1,1 , K1,2 , K1,3 , . . . , K1,n }). For the S-factor and Sn -factor problems mentioned earlier, Hell and Kirkpatrick have
shown the following.
Theorem 6.3 (Hell and Kirkpatrick [146]). The problem of finding a star factor S (or Sn ) in a graph is polynomial
if and only if the set of stars is sequential.
The clique partition number of a graph G is the smallest number cp(G) such that there exists a set of cp(G) cliques
in G such that the cliques form a partition of E(G). A graph G is chordal if every cycle in G of length greater than 3
has a chord.
Theorem 6.4 (Ma et al. [254]). The problem of determining cp(G) is NP-hard, for the class of K4 -free graphs and
for the class of chordal graphs. However, the problem is polynomial for the class of graphs which are both K4 -free
and chordal.
That the problem of determining the chromatic index of a graph is NP-complete was first proved by Holyer [166].
If G is bipartite however, a classical theorem of König states that
Theorem 6.5 (König [216,217]). If G is bipartite, then (G) = (G).
König’s proof yields an O(mn) algorithm to produce an optimal edge coloring. However, recently faster algorithms
have been invented. Presently, it seems that either an algorithm of Kapoor and Rizzi [194] or an algorithm of Schrijver
[328] is best, depending upon the relative sizes of |V (G)| and (G). If the bipartite graphs involved are, in addition,
regular, even faster algorithms exist. (See [318].)
Holyer also determined the complexity of the problem of partitioning E(G) into complete graphs all of the same
order greater than 2. (Compare this problem with the clique partition problem stated above.)
Theorem 6.6 (Holyer [167]). Suppose n 3. Then the problem of partitioning E(G) into copies of Kn is NP-complete.
Holyer used the above result to prove five other edge partition problems to be NP-complete in the same paper.
A still more general type of edge partition problem is the H-decomposition Problem.
The H-decomposition Problem: given a fixed graph H, can the edge set of an input graph G be partitioned into copies
of H?
A beautiful result of Gustavsson [130] (see also [15]) says that if G is “dense enough and large enough” (as a function
of H), then such an H-decomposition is always possible. Let gcd(G) denote the greatest common divisor of the degrees
of G.
Theorem 6.7. Let H be a graph with h edges. There exist constants N0 = N0 (H ) and = (H ) > 0, such that for all
n > N0 , if G is a graph on n vertices and m edges, with (G) n(1 − ), gcd(H )|gcd(G), and h|m, then G has an
H-decomposition.
The Holyer complexity results mentioned above deal with special cases of the H-decomposition problem. More
recently, Dor and Tarsi have proved the following.
Theorem 6.8 (Dor and Tarsi [75]). The H-decomposition problem is NP-complete whenever H contains a connected
component with three edges or more.
Bryś and Lonc [50] have finished off the complexity issue here by showing that, in all other cases, the H-decomposition
Problem is polynomial.
If both the graph G to be factored and the components of the factors are of some special types, sometimes factorization
can be guaranteed and even accomplished in polynomial time. An example is the following.
Theorem 6.9 (Bertram and Horák [33]). There is a polynomial algorithm which finds a factorization of any given
4-regular graph into two triangle-free 2-factors or else shows that such a factorization does not exist.
On the other hand, the same two authors pose the following:
Conjecture 6.10. The problems of
(a) recognizing which 2n-regular graphs decompose into two triangle-free n-factors, and
(b) recognizing which 2n-regular graphs decompose into n triangle-free 2-factors are both NP-complete for all n 3.
The following conjecture would follow from the truth of the 1-factorization conjecture.
Conjecture 6.11 (Hilton [152]). Let G be a d-regular simple graph of order 2n and let d = p1 + · · · + pr be a
partition of d. If d n, then G has a factorization into edge-disjoint subgraphs H1 ∪ · · · ∪ Hr , where Hi is regular of
degree pi .
The author proves the conjecture true in various special cases.

What if the subgraphs which partition E(G) are all to be isomorphic? Again, it is instructive to compare this partition
problem with the H-decomposition discussed above. Of course the difference is that here it is not specified ahead of
time what the isomorphic factor graphs are, but it is only specified that they be isomorphic.
If graph G admits a partition of its edge set into t isomorphic subgraphs, then we say that G is divisible by t. Of
course an obvious necessary condition for G to be divisible by t is that the number of graphs in the partition must divide
|E(G)|.
Following [91,92], let us call a graph G t-rational if either G is divisible by t or else t E(G)|.
The t-rational problem: Given a graph G and a positive integer t, is G t-rational?
In [366], it is shown that if r > 2t, then almost all labelled r-regular graphs cannot be factorized into t 2 isomorphic
subgraphs. But curiously, no examples of such regular non-factorizable graphs are known which satisfy the obvious
necessary divisibility condition: t||EG)|.
We provide several other sample results.
Theorem 6.12 (Ellingham and Wormald [94]). Let G be a multigraph and suppose t is an integer such that t (G).
Then G is t-rational.
Thus, by Vizing’s theorem, we have the next result.
Theorem 6.13. If G is r-regular and t r + 1, then G is t-rational.
It was shown by Harary et al. [137], and independently by Schönheim and Bialostocki [326], that Kn is t-rational
and Wang [364] and Quinn [316] independently showed that Kn,n,...,n is t-rational.
In [94] it is shown that every 3-regular graph can be partitioned into three isomorphic subgraphs; in [91] that every
4-regular graph can be partitioned into four such subgraphs and in [92] it is shown that for r even and r = 25, 27 or
r 29, every r-regular graph can be partitioned into r such subgraphs.
To the best of our knowledge, the computational complexity of the t-rational problem is currently unknown.
Plesník [309] has studied the complexity of the prescribed diameter and radius decompositions of the complete graph
discussed at the end of the preceding section. The diameter decomposition problem is to decompose the edge set of
a given graph into k disjoint factors with given diameters d1 , d2 , . . . , dk . If radii instead of diameters are prescribed,
then the corresponding problem is called the radius decomposition problem.
Theorem 6.14. (1) The diameter decomposition problem for graphs is NP-hard even in the case of two factors with
diameter bound 2;
(2) the diameter decomposition problem is NP-hard even for bipartite graphs in the case of two factors with diameter
bound 3;
(3) the radius decomposition problem for graphs is NP-hard even in the case of two factors with radius bound 2; and
(4) the diameter decomposition problem for digraphs is NP-hard even in the case of symmetric digraphs and two
factors with diameter bound 2.
7. Subgraph problems
Another variation on the theme of factors is represented by the following collection of problems. Suppose G and H
are two graphs on p vertices. When is H isomorphic to a subgraph of G? A sufficient condition involving minimum
degree , maximum degree and independence number was given by Catlin [52].
Theorem 7.1. Let G and H be two graphs on p vertices. If

(H )
(G)p − − 1,
2(H )
then H is isomorphic to a subgraph of G.
A different sort of result along this line was proved by Erdős and Hajnal [103].
Theorem 7.2. Given positive integers n and k, there exists a positive integer N such that for every integer n > N, for
every graph G of order n containing neither a clique of order c log n nor c log n independent vertices, and for
every graph H of order k we have that H is isomorphic to an induced subgraph of G.
It is trivial to embed any k-regular graph G in a (k + 1)-regular graph, if we omit the requirement that the k-regular
graph span the (k + 1)-regular graph. Just form the Cartesian product of G with a single edge. But what if one wants to
minimize the number of extra vertices needed? Let us denote by v(G) the minimum number of extra vertices needed.
Theorem 7.3 (Gardiner [123]). Let B be k-regular and have order n. Then
(i) if G has a 1-factor, v(G) = 0,

(ii) if G has no 1-factor and n and k are of opposite parity, v(G) = 1, while
(iii) if G has no 1-factor and n and k are of the same parity, then n < 2k and v(G) = k + 2.
Given a graph G, does it contain a k-regular subgraph? (Here again we do not require that the k-regular subgraph
span G.) This is sometimes referred to as the k-regular subgraph recognition problem. If k = 1 or 2, clearly the problem
is polynomial. The k-regular subgraph recognition problem has gained popularity due in large part to a conjecture of
Berge which was proved in [341,377].
Theorem 7.4. Every 4-regular simple graph contains a 3-regular subgraph.
It is interesting to note that these proofs do not provide an algorithm for finding the 3-regular subgraph.
More recently, it has been shown [62,310,53] that the k-regular subgraph recognition problem is, in fact, NP-complete
for all k 3. If the k-regular subgraph sought is, in particular, complete, then there is an O(nk ) algorithm [282] to solve
the problem, where n = |V (G)|.
A different result involving 3-regular subgraphs is given next. (See [16,17].) The proof uses number-theoretic
methods.
Theorem 7.5. If G is a multigraph in which all vertices have degree k or k + 1 and at least one vertex has degree at
least 5, then G contains a 3-regular subgraph.
A different type of subgraph problem is the subject of the next result (see [87]).
Theorem 7.6. If G is a graph with |V (G)|4k + 6 and (G) k + 2, then G contains k pairwise vertex-disjoint copies
of K1,3 .
Let us at least mention another large family of problems closely allied to factor and factorization problems, namely
so-called packing problems. Here instead of searching for a factor of a particular kind in a given graph G, one seeks a
subgraph of G of maximum order which admits a given factor. Hence, in a sense, packing problems generalize factor
problems. The problem of packing certain restricted graph families into other graphs has been studied widely. For
example, packing edges and triangles [66], cliques and maximal cliques [66,213], complete bipartite subgraphs [146],
Pk -matchings (that is perfect 2-matchings in which all cycles of length k are forbidden) [68], fractional matchings
[357,279,30] and dynamic matchings [298]. (See [65].) Again, space dictates that we refrain from pursuing this tack,
but instead we refer the interested reader to [247] for a nice survey of the state of the art. (But let the reader be warned
that the term “packing” means different things to different authors!)
This is just a tip of the iceberg. There are hundreds of papers in the literature dealing with a wide variety of
“subgraph problems” as well as “graph decompositions”. Space constraints dictate that we dare not venture further in
these directions. Instead the reader is referred to the survey papers [31,60,73,74,142,321] and the books [44,72,63].
8. Uncited references
[18,162].
Acknowledgment
The author wishes to thank Hajo Broersma, Mark Ellingham, Pavol Hell, Anthony Hilton, Mikio Kano, Haruhide
Matsuda and Tsuyoshi Nishimura for their kind assistance in compiling some of the source material for this paper. The
author is also grateful to the referees for their constructive comments.
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] R. Aharoni, A generalization of Tutte’s 1-factor theorem to countable graphs, J. Combin. Theory Ser. B 37 (1984) 199–209.
[3] R. Aharoni, König’s duality theorem for infinite bipartite graphs, J. London Math. Soc. 29 (1984) 1–12.
[4] R. Aharoni, Matchings in infinite graphs, J. Combin. Theory Ser. B 44 (1988) 87–125.
[5] R. Aharoni, Infinite matching theory, Discrete Math. 95 (1991) 5–22.
[6] R. Aharoni, M. Magidor, R. Shore, On the strength of König’s duality theorem for infinite bipartite graphs, J. Combin. Theory Ser. B 54 (1992)
257–290.
[7] R. Aharoni, C. Nash-Williams, Marriage in infinite societies, Progress in Graph Theory Academic Press, Toronto, 1984 pp. 71–79.
[8] R. Aharoni, C. Nash-Williams, S. Shelah, A general criterion for the existence of transversals, Proc. London Math. Soc. 47 (1983) 43–68.
[9] J. Akiyama, G. Exoo, F. Harary, Covering and packing in graphs III, cyclic and acyclic invariants, Math. Slovaca 30 (1980) 405–417.
[10] J. Akiyama, G. Exoo, F. Harary, Covering and packing in graphs, IV. Linear arboricity, Networks 11 (1981) 69–72.
[11] J. Akiyama, M. Kano, Path factors of a graph, Graphs and Applications, Boulder Colorada, 1982, Wiley, New York, 1984, pp. 1–21.
[12] J. Akiyama, M. Kano, Factors and factorizations of graphs—a survey, J. Graph Theory 9 (1985) 1–42.
[13] J. Akiyama, M. Kano, Almost-regular factorization of graphs, J. Graph Theory 9 (1985) 123–128.
[14] N. Alon, The linear arboricity of graphs, Israel J. Math. 62 (1988) 311–325.
[15] H. Alon, Y. Caro, R. Yuster, Packing and covering dense graphs, J. Combin. Des. 6 (1998) 451–472.
[16] N. Alon, S. Friedland, G. Kalai, Regular subgraphs of almost regular graphs, J. Combin. Theory Ser. B 37 (1984) 79–91.
[17] N. Alon, S. Friedland, G. Kalai, Every 4-regular graph plus an edge contains a 3-regular subgraph, J. Combin. Theory Ser. B 37 (1984)
92–93.
[18] N. Alon, C. McDiarmid, B. Reed, Star arboricity, Combinatorica 12 (1992) 375–380.
[19] N. Alon, V. Teague, N. Wormald, Linear arboricity and linear k-arboricity of regular graphs, Graphs Combin. 17 (2001) 11–16.
[20] A. Amahashi, On factors with all degrees odd, Graphs Combin. 1 (1985) 111–114.
[21] A. Amahashi, M. Kano, On factors with given components, Discrete Math. 42 (1982) 1–6.
[22] I. Anderson, Sufficient conditions for matching, Proc. Edinb. Math. Soc. 18 (1972/73) 129–136.
[23] K. Ando, Y. Egawa, A. Kaneko, K. Kawarabayashi, H. Matsuda, Path factors in claw-free graphs, Discrete Math. 243 (2002) 195–200.
[24] R. Anstee, An algorithmic proof of Tutte’s f -factor theorem, J. Algorithms 6 (1985) 112–131.
[25] R. Anstee, Simplified existence theorems for (g, f )-factors, Discrete Appl. Math. 27 (1990) 29–38.
[26] R. Anstee, Matching theory: fractional to integral, New Zealand J. Math. 21 (1992) 17–32.
[27] R. Anstee, Y. Nam, More sufficient conditions for a graph to have factors, Discrete Math. 184 (1998) 15–24.
[28] R. Anstee, Y. Nam, Convexity of degree sequences, J. Graph Theory 30 (1999) 147–156.
[29] F. Bäbler, Über die Zerlegung regulärer Streckencomplexe ungerader Ordnung, Comment. Math. Helv. 10 (1938) 275–287.
[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.
[31] L. Beineke, Graph decompositions, Congress. Numer. 115 (1996) 213–226.
[32] J.-C. Bermond, M. Las Vergnas, Regular factors in nearly regular graphs, Discrete Math. 50 (1984) 9–13.
[33] E. Bertram, P. Horák, Decomposing 4-regular graphs into triangle-free 2-factors, SIAM J. Discrete Math. 10 (1997) 309–317.
[34] T. Biedl, P. Bose, E. Demaine, A. Lubiw, Efficient algorithms for Petersen’s matching theorem, J. Algorithms 38 (2001) 110–134.
[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.
[36] B. Bollobás, Extremal Graph Theory, Academic Press, London, New York, 1978 xx+488pp.
[37] B. Bollobás, Random Graphs, Academic Press Inc., Harcourt Brace Jovanovich, Publishers, London, 1985.
[38] B. Bollobás, Random Graphs, second ed., Cambridge University Press, Cambridge, 2001.
[39] B. Bollobás, C. Cooper, T. Fenner, A. Frieze, Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least k, J. Graph
Theory 34 (2000) 42–59.
[40] B. Bollobás, T. Fenner, A. Frieze, Hamilton cycles in random graphs of minimal degree at least k, A tribute to Paul Erdős, Cambridge University
Press, Cambridge, 1990 pp. 59–95.
[41] B. Bollobás, B. McKay, The number of matchings in random regular graphs and bipartite graphs, J. Combin. Theory Ser. B 41 (1996) 80–91.
[42] B. Bollobás, A. Saito, N. Wormald, Regular factors of regular graphs, J. Graph Theory 9 (1985) 97–103.
[43] J. Bosák, Disjoint factors of diameter two in complete graphs, J. Combin. Theory Ser. B 16 (1974) 57–63.
[44] J. Bosák, Decompositions of Graphs, Kluwer Academic Publishers Group, Dordrecht, 1990.
[45] J. Bosák, A. Rosa, Š. Znám, On decompositions of complete graphs into factors with given diameters, in: Theory of Graphs, Proceedings of
Colloquium, Tihany, 1966, Academic Press, New York, 1968, pp. 37–56.
[46] J.-M. Bourjolly, W. Pulleyblank, König-Egerváry graphs, 2-bicritical graphs and fractional matchings, Discrete Appl. Math. 24 (1989)
63–82.
[47] S. Brandt, G. Chen, R. Faudree, R.J. Gould, L. Lesniak, Degree conditions for 2-factors, J. Graph Theory 24 (1997) 165–173.
[48] L. Brègman, Certain properties of nonnegative matrices and their permanents, Dokl. Akad. Nauk SSSR 211 (1973) 27–30 (in Russian);
L. Brègman, Soviet Math. Dokl. 14 (1973) 945–949 (English translation).
[49] R. Brualdi, Strong transfinite versions of König’s duality theorem, Monatsh. Math. 75 (1971) 106–110.
[50] K. Bryś, Z. Lonc, A complete solution of a Holyer problem, in: Proceedings of the Fourth Twente Workshop on Graphs and Combinatorial
Optimization, University of Twente, Enschede, The Netherlands, 1995.
[51] D. Cariolaro, A. Hilton, Class 1 graphs associated with regular graphs of high degree, Congr. Numer. 159 (2002) 133–142.
[52] P. Catlin, Subgraphs of graphs, I, Discrete Math. 10 (1974) 225–233.
[53] F. Cheah, D. Corneil, The complexity of regular subgraph recognition, Discrete Appl. Math. 27 (1990) 59–68 Addendum: Discrete Appl.
Math. 31 (1990) 309.
[54] C. Chen, f -star factors with given properties, Acta Math. Sci. (Chinese) 11 (1991) 36–43.
[55] C. Chen, Y. Egawa, M. Kano, Star factors with given properties, Ars Combin. 28 (1989) 65–70.
[56] C. Chen, M. Kano, Odd and even factors with given properties, Chinese Quart. J. Math. 7 (1992) 65–71.
[57] G. Chen, J. Faudree, R. Gould, A. Saito, 2-factors in claw-free graphs, Discuss. Math. Graph Theory 20 (2000) 165–172.
[58] A. Chetwynd, A. Hilton, Star multigraphs with three vertices of maximum degree, Math. Proc. Cambridge Philos. Soc. 100 (1986) 303–317.
[59] A. Chetwynd, A. Hilton, 1-factorizing regular graphs with high degree: an improved bound, Discrete Math. 75 (1989) 103–112.
[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.
[61] V. Chvátal, Tough graphs and hamiltonian circuits, Discrete Math. 5 (1973) 215–228.
[62] V. Chvátal, H. Fleischner, J. Sheehan, C. Thomassen, Three-regular subgraphs of four-regular graphs, J. Graph Theory 3 (1979) 371–386.
[63] C. Colbourn, A. Rosa, Triple Systems, The Clarendon Press, Oxford University Press, New York, 1999.
[64] C. Cooper, A. Frieze, M. Molloy, B. Reed, Perfect matchings in random r-regular, s-uniform hypergraphs, Combin. Probab. Comput. 5 (1996)
1–14.
[65] G. Cornuéjols, D. Hartvigsen, An extension of matching theory, J. Combin. Theory Ser. B 40 (1986) 285–296.
[66] G. Cornuéjols, D. Hartvigsen, W. Pulleyblank, Packing subgraphs in a graph, Oper. Res. Lett. 1 (1982) 139–143.
[67] G. Cornuéjols, W. Pulleyblank, Perfect triangle-free 2-matchings, Combinatorial optimization II (Proceedings of Conference University of
East Anglia, Norwich, 1979), Math. Program. Stud. 13 (1980) 1–7.
[68] G. Cornuéjols, W. Pulleyblank, Critical graphs, matchings and tours or a hierarchy of relaxations for the traveling salesman problem,
Combinatorica 3 (1983) 35–52.
[69] K. Corrádi, A. Hajnal, On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hungar. 14 (1963) 423–439.
[70] I. Csiszár, J. Körner, Graph decomposition: a new key to coding theorems, IEEE Trans. Inform. Theory 27 (1981) 5–12.
[71] Y. Cui, M. Kano, Some results on odd factors of graphs, J. Graph Theory 12 (1988) 327–333.
[72] R. Diestel, Graph decompositions. A Study in Infinite Graph Theory, The Clarendon Press, Oxford University Press, New York, 1990.
[73] R. Diestel, Decomposing infinite graphs, Contemporary Methods in Graph Theory, Bibliographisches Inst., Mannheim, 1990, 261–289.
[74] R. Diestel, Decomposing infinite graphs, Discrete Math. 95 (1991) 69–89.
[75] D. Dor, M. Tarsi, Graph decomposition is N P -complete: a complete proof of Holyer’s conjecture, SIAM J. Comput. 26 (1997) 1166–1187.
[76] J. Edmonds, Paths, trees and flowers, Canad. J. Math. 17 (1965) 449–467.
[77] J. Edmonds, E. Johnson, Matching: a well solved class of integer linear programs, Combinatorial Structures and their Applications, Gordon
and Breach, New York, 1970 pp. 89–92.
[78] Y. Egawa, Era’s conjecture on [k, k + 1]-factorizations of regular graphs, Ars Combin. 21 (1986) 217–220.
[79] Y. Egawa, H. Enomoto, Sufficient conditions for the existence of k-factors, Recent Studies in Graph Theory, Vishwa, Gulbarga, 1989
pp. 96–105.
[80] Y. Egawa, H. Enomoto, R. Faudree, H. Li, I. Schiermeyer, Two-factors each component of which contains a specified vertex, J. Graph Theory
43 (2003) 188–198.
[81] Y. Egawa, H. Enomoto, A. Saito, Factors and induced subgraphs, Discrete Math. 68 (1988) 179–189.
[82] Y. Egawa, H. Enomoto, N. Tokushige, Graph decompositions through prescribed vertices without isolates, Ars Combin. 62 (2002) 189–205.
[83] Y. Egawa, R. Faudree, E. Györi, Y. Ishigami, R. Schelp, H. Wang, Vertex-disjoint cycles containing specified edges, Graphs Combin. 16
(2000) 81–92.
[84] Y. Egawa, M. Kano, Sufficient conditions for graphs to have (g, f )-factors, Discrete Math. 151 (1996) 87–90.
[85] Y. Egawa, M. Kano, A.K. Kelmans, Star partitions of graphs, J. Graph Theory 25 (1997) 185–190.
[86] Y. Egawa, K. Ota, Regular factors in K1,n -free graphs, J. Graph Theory 15 (1991) 337–344.
[87] Y. Egawa, K. Ota, Vertex-disjoint claws in graphs, Discrete Math. 197/198 (1999) 225–246.
[88] Y. Egawa, K. Ota, K1,3 -factors in graphs, preprint, 2002.
[89] G. Egoryc̀ev, Solution of the van der Waerden problem for permanents, Sibirsk. Mat. Zh. 22 (1981) 65–71 225 (in Russian).
[90] G. Egoryc̀ev, The solution of van der Waerden’s problem for permanents, Adv. Math. 42 (1981) 299–305.
[91] M. Ellingham, Isomorphic factorizations of regular graphs of even degree, J. Austral. Math. Soc. Ser. A 44 (1988) 402–420.
[92] M. Ellingham, Isomorphic factorization of r-regular graphs into r parts, Discrete Math. 69 (1988) 19–34.
[93] M. Ellingham, Y. Nam, H.-J. Voss, Connected (g, f )-factors, J. Graph Theory 39 (2002) 62–75.
[94] M. Ellingham, N. Wormald, Isomorphic factorization of regular graphs and 3-regular multigraphs, J. London Math. Soc. 37 (1988) 14–24.
[95] M. El-Zahár, On circuits in graphs, Discrete Math. 50 (1984) 227–230.
[96] H. Enomoto, Graph decompositions without isolated vertices, J. Combin. Theory Ser. B 63 (1995) 111–124.
[97] H. Enomoto, B. Jackson, P. Katerinis, A. Saito, Toughness and the existence of k-factors, J. Graph Theory 9 (1985) 87–95.
[98] H. Enomoto, S. Matsunaga, Graph decompositions without isolated vertices II, J. Math. Soc. Japan 49 (1997) 161–180.
[99] H. Enomoto, S. Matsunaga, Graph decompositions without isolated vertices III, J. Graph Theory 24 (1997) 155–164.
[100] H. Enomoto, K. Ota, M. Kano, A sufficient condition for a bipartite graph to have a k-factor, J. Graph Theory 12 (1988) 141–151.
[101] H. Enomoto, T. Tokuda, Complete-factors and f -factors, Discrete Math. 220 (2000) 239–242.
[102] H. Era, Semiregular factorizations of regular graphs, Graphs and Applications, Boulder, Colorado, 1982, Wiley, 1985 pp. 101–116.
[103] P. Erdő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] P. Erdős, A. Rényi, On the existence of a factor of degree one of a connected random graph, Acta Math. Acad. Sci. Hungar. 17 (1966)
359–368.
[105] D. Falikman, Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki 29 (1981) 931–938 957
(in Russian);
D. Falikman, Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix, Math. Notes 29 (1981) 475–479
[106] R. Faudree, O. Favaron, E. Flandrin, H. Li, Z. Liu, On 2-factors in claw-free graphs, Discrete Math. 206 (1999) 131–137.
[107] C. Feng, Existence for k-factors in claw-free graphs, Xinan Shifan Daxue Xuebao Ziran Kexue Ban 24 (1999) 276–279 (in Chinese).
[108] S. Fiorini, A bibliographic survey of edge-colourings, J. Graph Theory 2 (1978) 93–106.
[109] S. Fiorini, R. Wilson, Edge-colourings of graphs, Research Notes in Mathematics, vol. 16, Pitman, London, 1977.
[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.
[111] C. Fremuth-Paeger, D. Jungnickel, Balanced network flows, I. A unifying framework for design and analysis of matching algorithms, Networks
33 (1999) 1–28.
[112] C. Fremuth-Paeger, D. Jungnickel, Balanced network flows, II. Simple augmentation algorithms, Networks 33 (1999) 29–41.
[113] C. Fremuth-Paeger, D. Jungnickel, Balanced network flows, III. Strongly polynomial augmentation algorithms, Networks 33 (1999) 43–56.
[114] C. Fremuth-Paeger, D. Jungnickel, Balanced network flows, IV. Duality and structure theory, Networks 37 (2001) 194–201.
[115] A. Frieze, S. Janson, Perfect matchings in random s-uniform hypergraphs, Random Structures Algorithms 7 (1995) 41–57.
[116] G. Frobenius, Über Matrizen aus nicht negativen Elementen, Sitzungsber. König. Preuss. Akad. Wiss. 26 (1912) 456–477.
[117] D. Fronček, Decompositions of complete bipartite and tripartite graphs into self-complementary factors with finite diameters, Graphs Combin.
12 (1996) 305–320.
[118] S. Fujita, Vertex-disjoint K1,t ’s in graphs, Ars Combin. 64 (2002) 211–223.
[119] D. Fulkerson, A. Hoffman, M. McAndrew, Some properties of graphs with multiple edges, Canad. J. Math. 17 (1965) 166–177.
[120] H. Gabow, H. Kaplan, R. Tarjan, Unique maximum matching algorithms, Annual ACM Symposium on Theory of Computing, Atlanta, GA,
1999 (electronic), ACM, New York, 1999 pp. 70–78.
[121] H. Gabow, H. Kaplan, R. Tarjan, Unique maximum matching algorithms, J. Algorithms 40 (2001) 159–183.
[122] H. Gabow, R. Tarjan, Faster scaling algorithms for general graph-matching problems, J. Assoc. Comput. Mach. 38 (1991) 815–853.
[123] A. Gardiner, Embedding k-regular graphs in k + 1-regular graphs, J. London Math. Soc. 28 (1983) 393–400.
[124] M. Garey, D. Johnson, Computers and Intractability, A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979.
[125] M. Garey, D. Johnson, R. Tarjan, The planar hamiltonian circuit problem is NP-complete, SIAM J. Comput. 5 (1976) 704–714.
[126] R. Gould, Updating the hamiltonian problem—a survey, J. Graph Theory 15 (1991) 121–157.
[127] R. Gould, Advances on the Hamiltonian problem—a survey, Graphs Combin. 19 (2003) 7–52.
[128] F. Guldan, Some results on linear arboricity, J. Graph Theory 10 (1986) 505–509.
[129] G. Gunther, B. Hartnell, D. Rall, Star-factors and k-bounded total domination, Networks 27 (1996) 197–201.
[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] M. Habib, B. Péroche, Some problems about linear arboricity, Discrete Math. 41 (1982) 219–220.
[133] P. Hajnal, Partition of graphs with condition on the connectivity and minimum degree, Combinatorica 3 (1983) 95–99.
[134] M. Hall, Distinct representatives of subsets, Bull. Amer. Math. Soc. 54 (1948) 922–926.
[135] P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935) 26–30.
[136] F. Harary, Covering and packing graphs I, Ann. New York Acad. Sci. 175 (1970) 198–205.
[137] F. Harary, R. Robinson, N. Wormald, Isomorphic factorisations, I. Complete graphs, Trans. Amer. Math. Soc. 242 (1978) 243–260.
[138] F. Harary, W. Wallis, Isomorphic factorizations, II. Combinatorial designs, Congress. Numer. XIX (1977) 13–28.
[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.
[141] K. Heinrich, P. Hell, D. Kirkpatrick, G. Liu, Communication: a simple existence criterion for (g < f )-factors, Discrete Math. 85 (1990)
313–317.
[142] P. Hell, Graph packings, Discrete Mathematics, Electronic Notes, 2000.
[143] P. Hell, D. Kirkpatrick, On generalized matching problems, Inform. Process. Lett. 12 (1981) 33–35.
[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] P. Hell, D. Kirkpatrick, Packings by complete bipartite graphs, SIAM J. Algebraic Discrete Methods 7 (1986) 199–209.
[147] P. Hell, D. Kirkpatrick, J. Kratochvíl, I. Kříž, On restricted two-factors, SIAM J. Discrete Math. 1 (1988) 472–484.
[148] P. Hell, D. Kirkpatrick, B. Li, Rounding in symmetric matrices and undirected graphs, Discrete Appl. Math. 70 (1996) 1–21.
[149] G. Hendry, Maximum graphs with a unique k-factor, J. Combin. Theory Ser. B 37 (1984) 53–63.
[150] P. Híc, D. Palumbíny, Isomorphic factorisations of complete graphs into factors with a given diameter, Math. Slovaca 37 (1987) 247–254.
[151] A. Hilton, Canonical edge-colourings of locally finite graphs, Combinatorica 2 (1982) 37–51.
[152] A. Hilton, Factorizations of regular graphs of high degree, J. Graph Theory 9 (1985) 193–196.
[153] A. Hilton, Recent progress on edge-colouring graphs, Discrete Math. 64 (1987) 303–307.
[154] A. Hilton, Recent results on edge-colouring graphs, with applications to the total-chromatic number, J. Combin. Math. Combin. Comput.
3 (1988) 121–134.
[155] A. Hilton, (r, r + 1)-factorizations of (d, d + 1)-graphs, submitted.
[156] A. Hilton, F. Holroyd, C. Zhao, The overfull conjecture and the conformability conjecture, Discrete Math. 241 (2001) 343–361.
[157] A. Hilton, W. Johnstone, Some problems about r-factorizations of complete graphs, J. Combin. Math. Combin. Comput. 35 (2000) 3–49.
[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.
[159] D. Hoffman, C. Rodger, On the number of edge-disjoint one factors and the existence of k-factors in complete multipartite graphs, Discrete
Math. 160 (1996) 177–187.
[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.
[161] A. Hoffmann, Regular factors in regular multipartite graphs, Discrete Math. 258 (2002) 43–62.
[162] A. Hoffmann, Regular factors in connected regular graphs, Ars Combin. 68 (2003) 235–242.
[163] A. Hoffmann, L. Volkmann, Extremal bipartite graph with a unique k-factor, preprint, 2003.
[164] A. Hoffmann, L. Volkmann, On unique k-factors and unique [1, k]-factors in graphs, Discrete Math. 278 (2004) 127–138.
[165] A. Hoffmann, L. Volkmann, On regular factors in regular graphs with small radius, Electron. J. Combin. 11, 2004; Research Paper 7, 7pp
(electronic).
[166] I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718–720.
[167] I. Holyer, The NP-completeness of some edge partition problems, SIAM J. Comput. 10 (1981) 713–717.
[168] M. Holz, K.-P. Podewski, K. Steffens, Injective Choice Functions, Lecture Notes in Mathematics, vol. 1238, Springer, Berlin, 1987.
[169] P. Hrnčiar, On decompositions of complete graphs into three factors with given diameters, Czechoslovak Math. J. 40 (115) (1990) 388–396.
[170] T. Iida, T. Nishimura, An ore-type condition for the existence of k-factors in graphs, Graphs Combin. 7 (1991) 353–361.
[171] T. Iida, T. Nishimura, Neighborhood conditions and k-factors, Tokyo J. Math. 20 (1997) 411–418.
[172] Y. Ishigami, T. Jiang, Vertex-disjoint cycles containing prescribed vertices, J. Graph Theory 42 (2003) 276–296.
[173] B. Jackson, R. Whitty, A note concerning graphs with unique f-factors, J. Graph Theory 13 (1989) 577–580.
[174] S. Janson, The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph, Combin. Probab. Comput. 3 (1994)
97–126.
[175] S. Janson, T. Łuczak, A. Ruciński, Random Graphs, Wiley Interscience, New York, 2000.
[176] T. Jensen, B. Toft, Graph Coloring Problems, Wiley-Interscience, New York, 1995.
[177] P. Johann, On the structure of graphs with a unique k-factor, J. Graph Theory 35 (2000) 227–243.
[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] R. Johansson, On the bipartite case of El-Zahár’s conjecture, Discrete Math. 219 (2000) 123–134.
[180] A. Kaneko, 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 (2003) 195–218.
[181] A. Kaneko, A. Kelmans, T. Nishimura, On packing 3-vertex paths in a graph, J. Graph Theory 36 (2001) 175–197.
[182] A. Kaneko, K. Yoshimoto, On a 2-factor with a specified edge in a graph satisfying the Ore condition, Discrete Math. 257 (2002) 445–461.
[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] M. Kano, [a, b]-factorization of a graph, J. Graph Theory 9 (1985) 129–146.
[185] M. Kano, [a, b]-factorizations of nearly bipartite graphs, in: Graph Theory with Applications to Algorithms and Computer Science, Kalamazoo,
Michigan, 1984, Wiley-Interscience Publication, Wiley, New York, 1985, pp. 471–474.
[186] M. Kano, Factors of regular graphs, J. Combin. Theory Ser. B 41 (1986) 27–36.
[187] M. Kano, A sufficient condition for a graph to have [a, b]-factors, Graphs Combin. 6 (1990) 245–251.
[188] M. Kano, Sufficient conditions for a graph to have factors, Discrete Math. 80 (1990) 159–165.
[189] M. Kano, Current results and problems on factors of graphs, in: Combinatorics, Graph Theory, Algorithms and Applications, Beijing, 1993,
World Scientific Publishing, River Edge, New Jersey, 1994, pp. 93–98.
[190] M. Kano, G. Katona, Odd subgraphs and matchings, Discrete Math. 250 (2002) 265–272.
[191] M. Kano, G. Katona, Structure theorem and algorithm on (1, f )-odd subgraphs, Discrete Math., 2004, to appear.
[192] M. Kano, A. Saito, [a, b]-factors of graphs, Discrete Math. 47 (1983) 113–116.
[193] M. Kano, N. Tokushige, Binding numbers and f -factors of graphs, J. Combin. Theory Ser. B 54 (1992) 213–221.
[194] A. Kapoor, R. Rizzi, Edge-coloring bipartite graphs, J. Algorithms 34 (2000) 390–396.
[195] M. Karoński, A review of random graphs, J. Graph Theory 6 (1982) 349–389.
[196] M. Karoński, Random graphs, Handbook of Combinatorics, vol. 12, Elsevier, Amsterdam, 1995, pp. 351–380.
[197] R. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, Plenum Press, New York, 1972,
pp. 85–103.
[198] R. Karp, On the computational complexity of combinatorial problems, Networks 5 (1975) 45–68.
[199] P. Katerinis, Some results on the existence of 2n-factors in terms of vertex deleted subgraphs, Ars Combin. 16-B (1983) 271–277.
[200] P. Katerinis, Some conditions for the existence of f -factors, J. Graph Theory 9 (1985) 513–521.
[201] P. Katerinis, A Chvátal–Erdős condition for an r-factor in a graph, Ars Combin. 20 (1985) 185–191.
[202] P. Katerinis, Two sufficient conditions for a 2-factor in a bipartite graph, J. Graph Theory 11 (1987) 1–6.
[203] P. Katerinis, Toughness of graphs and the existence of factors, Discrete Math. 80 (1990) 81–92.
[204] P. Katerinis, Minimum degree of bipartite graphs and the existence of k-factors, Graphs Combin. 6 (1990) 253–258.
[205] P. Katerinis, N. Tsikopoulos, Minimum degree and F -factors in graphs, New Zealand J. Math. 29 (2000) 33–40.
[206] P. Katerinis, N. Tsikopoulos, Independence number, connectivity and f -factors, Utilitas Math. 57 (2000) 81–95.
[207] P. Katerinis, D. Woodall, Binding numbers of graphs and the existence of k-factors, Quart. J. Math. 38 (1987) 221–228.
[208] K. Kawarabayashi, K4− -factor in a graph, J. Graph Theory 39 (2002) 111–128.
[209] K. Kawarabayashi, H. Matsuda, Y. Oda, K. Ota, Path factors in cubic graphs, J. Graph Theory 39 (2002) 188–193.
[210] A. Kelmans, Optimal packing of induced stars in a graph, Discrete Math. 173 (1997) 97–127.
[211] Z. Király, C4 -free f-factors in bipartite graphs, Egerváry research group on combinatorial optimization, Technical Report 2001-13, Budapest,
Hungary, November, 1999.
[212] D. Kirkpatrick, P. Hell, On the completeness of a generalized matching problem, in: Conference Record of the Tenth Annual ACM Symposium
on Theory of Computing (San Diego, California, 1978), ACM, New York, 1978, pp. 240–245.
[213] D. Kirkpatrick, P. Hell, On the complexity of general graph factor problems, SIAM J. Comput. 12 (1983) 601–609.
[214] D. Kleitman, D. Wang, Algorithms for constructing graphs and digraphs with given valences and factors, Discrete Math. 6 (1973) 79–88.
[215] W. Kocay, D. Stone, Balanced network flows, Bull. Inst. Combin. Appl. 7 (1993) 17–32.
[216] D. König, Über Graphen und ihre Andwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916) 453–465.
[217] D. König, Graphok és alkalmazásuk a determinánsok és a halmazok elméletére, Math. Termész. Ért 34 (1916) 104–119.
[218] D. König, Graphs and matrices, Mat. Fiz. Lapok 38 (1931) 116–119 (in Hungarian).
[219] D. König, Über trennende Knotenpunkte in Graphen (nebst. Anwendungen auf Determinanten und Matrizen), Acta Sci. Math. (Szeged)
6 (1933) 155–179.
[220] K. Kotani, Factors and connected induced subgraphs, Graphs Combin. 17 (2001) 511–515.
[221] A. Kotzig, On the theory of finite graphs with a linear factor, I, Mat.-Fyz. Časopis Slovensk. Akad. Vied 9 (1959) 73–91 (Slovak).
[222] A. Kotzig, A. Rosa, Decomposition of complete graphs into isomorphic factors with a given diameter, Bull. London Math. Soc. 7 (1975)
51–57.
[223] M. Kouider, M. Mahéo, Connected [a, b]-factors in graphs, Combinatorica 22 (2002) 71–82.
[224] M. Kouider, P. Vestergaard, Survey on connected factors in graphs, Graphs Combin. 21 (2005) 1–26.
[225] S. Kundu, The k-factor conjecture is true, Discrete Math. 6 (1973) 367–376.
[226] J. Lan, W.-K. Chen, On f -factors of a graphs, J. Franklin Inst. 320 (1985) 55–62.
[227] M. Las Vergnas, A note on matchings in graphs, Colloque sur la Théorie des Graphes (Paris, 1974), Cahiers Centre Études Recherche Opér.
17 (1975) 257–260.
[228] M. Las Vergnas, An extension of Tutte’s 1-factor theorem, Discrete Math. 23 (1978) 241–255.
[229] U. Lenkewitz, L. Volkmann, Neighbourhood and degree conditions for the existence of regular factors, Ars Combin. 42 (1996) 33–47.
[230] G. Li, Z. Liu, On connected factors in K1,3 -free graphs, Acta Math. Appl. Sinica 14 (1998) 43–47.
[231] G. Li, B. Zhu, C. Chen, On connected [k, k + 1]-factors in claw-free graphs, Ars Combin. 62 (2002) 207–219.
[232] J. Li, A neighborhood condition for graphs to have [a, b]-factors, J. Math. Study 35 (2002) 371–375.
[233] J. Li, On neighborhood condition for graphs to have [a, b]-factors, Discrete Math. 260 (2003) 217–221.
[234] J. Li, H. Deng, Sufficient conditions for the existence of fractional factors of graphs, J. Nat. Sci. Hunan Norm. Univ. 26 (2003) 25–28.
[235] Y. Li, M. Kano, C. Mao-cheng, A [k, k + 1]-factor containing given Hamiltonian cycle, Sci. China Ser. A 41 (1998) 933–938.
[236] Y. Li, M. Kano, C. Mao-cheng, A [k, k + 1]-factor containing given Hamiltonian cycle, Electron. J. Combin. 6 (1999) Research Paper 4, 8pp
(electronic).
[237] Y. Li, C. Mao-cheng, A degree condition for the existence of connected factors, Australas. J. Combin. 14 (1996) 77–83.
[238] Y. Li, C. Mao-cheng, A degree condition for a graph to have [a, b]-factors, J. Graph Theory 27 (1998) 1–6.
[239] C. Lindner, E. Mendelsohn, A. Rosa, On the number of 1-factorizations of the complete graph, J. Combin. Theory Ser. B 20 (1976) 265–282.
[240] C. Little, D. Grant, D. Holton, On defect d-matchings in graphs, Discrete Math. 13 (1975) 41–54;
Erratum: on defect-d matching in graphs, Discrete Math. 14 (1976) 203.
[241] G. Liu, On f-covered graphs, Seventeenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1987), Congr.
Numer. 61 (1988) 81–86.
[242] G. Liu, On (g, f )-covered graphs, Acta Math. Sci. (English edition) 8 (1988) 181–184.
[243] G. Liu, On [a, b]-covered graphs, J. Combin. Math. Combin. Comput. 5 (1989) 14–22.
[244] G. Liu, L. Zhang, Maximum fractional (0, f )-factors of graphs, Math. Applic. (Wuhan) 13 (2000) 31–35.
[245] G. Liu, L. Zhang, Fractional (g, f )-factors of graphs, Acta Math. Sci. Ser. B (English edition) 21 (2001) 541–545.
[246] Y. Liu, G. Liu, The fractional matching numbers of graphs, Networks 40 (2002) 228–231.
[247] M. Loebl, S. Poljak, Subgraph packing—a survey, Topics in Combinatorics and Graph Theory (Oberwolfach, 1990), Physica, Heidelberg,
1990, pp. 491–503.
[248] Z. Lonc, On the complexity of some edge-partition problems for graphs, Discrete Appl. Math. 70 (1996) 177–183.
[249] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237–238.
[250] L. Lovász, Subgraphs with prescribed valencies, J. Combin. Theory 8 (1970) 391–416.
[251] L. Lovász, Valencies of graphs with 1-factors, Period. Math. Hungar. 5 (1974) 149–151.
[252] L. Lovász, A homology theory for spanning trees of a graph, Acta Math. Acad. Sci. Hungar. 30 (1977) 241–251.
[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] S. Ma, W. Wallis, J. Wu, The complexity of the clique partition number problem, 19th Southeastern Conference on Combinatorics, Graph
Theory, and Computing (Baton Rouge, LA, 1988), Congr. Numer. 67 (1988) 59–66.
[255] Y. Ma, G. Liu, Isolated toughness and the existence of fractional factors, Acta Math. Appl. Sin. 26 (2003) 133–140.
[256] E. Mahmoodian, On factors of a graph, Canad. J. Math. 29 (1977) 438–440.
[257] C. Mao-cheng, [a, b]-factorizations of graphs, J. Graph Theory 15 (1991) 283–301.
[258] C. Mao-cheng, A degree condition for the existence of connected [k, k + 1]-factors, Systems Sci. Math. Sci. 8 (1995) 364–368.
[259] C. Mao-cheng, Connected [k, k + 1]-factors of graphs, Discrete Math. 169 (1997) 1–16.
[260] I. Marková, Decomposition of complete graphs into factors with diameter two, Acta Math. Univ. Comenian. 56/57 (1989) 235–241.
[261] N. Martin, Complete bipartite factorisations by complete bipartite graphs, Discrete Math. 167/168 (1997) 461–480.
[262] N. Martin, Complete bipartite factorisations of Kn,n , Discrete Math. 266 (2003) 353–375.
[263] H. Matsuda, A neighborhood condition for graphs to have [a, b]-factors, Discrete Math. 224 (2000) 289–292.
[264] H. Matsuda, A neighborhood condition for graphs to have [a, b]-factors. II, Graphs Combin. 18 (2002) 763–768.
[265] H. Matsuda, Degree conditions for the existence of [k, k + 1]-factors containing a given Hamiltonian cycle, Australas. J. Combin. 26 (2002)
273–281.
[266] H. Matsuda, Degree conditions for Hamiltonian graphs to have [a, b]-factors containing a given Hamiltonian cycle, Discrete Math. 280 (2004)
241–250.
[267] H. Matsuda, Regular factors containing a given Hamiltonian cycle, preprint, 2003.
[268] P. McCarthy, Matchings in graphs II, Discrete Math. 11 (1975) 141–145.
[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] P. McCarthy, Matchings in infinite graphs, Czechoslovak Math. J. 28 (1978) 245–251.
[271] C. McDiarmid, B. Reed, Linear arboricity of random regular graphs, Random Structures Algorithms 1 (1990) 443–445.
[272] C. McDiarmid, B. Reed, Almost every graph can be covered by /2 linear forests, Combin. Probab. Comput. 4 (1995) 257–268.
[273] E. Mendelsohn, A. Rosa, On some properties of 1-factorizations of complete graphs, Congress. Numer. XXIII–XXIV (1979) 739–752.
[274] E. Mendelsohn, A. Rosa, One-factorizations of the complete graphs—a survey, J. Graph Theory 9 (1985) 43–65.
[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] M. Molloy, The probabilistic method, Algorithms Combin. 16 (1998) 1–35.
[277] M. Molloy, B. Reed, Graph Colouring and the Probabilistic Method, Springer, Berlin, 2002.
[278] M. Molloy, H. Robalewska, R. Robinson, N. Wormald, 1-factorizations of random regular graphs, Random Structures Algorithms 10 (1997)
305–321.
[279] J. Mühlbacher, F-factors of graphs: a generalized matching problem, Inform. Process. Lett. 8 (1979) 207–214.
[280] J. Mühlbacher, F. Steinparz, G. Tinhofer, On certain classes of fractional matchings, Discrete Appl. Math. 9 (1984) 235–244.
[281] Y. Nam, Ore-type condition for the existence of connected factors, preprint, February, 2000.
[282] J. Nešetřil, J. Poljak, On the complexity of the subgraph problem, Comment. Math. Univ. Carolin. 26 (1985) 415–419.
[283] F. Niedermeyer, f-optimal factors of infinite graphs, Discrete Math. 95 (1991) 231–254.
[284] F. Niedermeyer, K-P. Podewski, Matchable infinite graphs, J. Combin. Theory Ser. B 62 (1994) 213–227.
[285] L. Niepel, On decompositions of complete graphs into factors with given diameters and radii, Math. Slovaca 30 (1980) 3–11.
[286] T. Niessen, Nash-Williams conditions and the existence of k-factors, Ars Combin. 34 (1992) 251–256.
[287] T. Niessen, A characterization of graphs having all (g, f )-factors, J. Combin. Theory Ser. B 72 (1998) 152–156.
[288] T. Niessen, B. Randerath, Regular factors of simple regular graphs and factor-spectra, Discrete Math. 185 (1998) 89–103.
[289] T. Niessen, L. Volkmann, Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree, J. Graph
Theory 14 (1990) 225–246.
[290] T. Nishimura, Independence number, connectivity and degree factors, SUT J. Math. 25 (1989) 79–87.
[291] T. Nishimura, Independence number connectivity and r-factors, J. Graph Theory 13 (1989) 63–69.
[292] T. Nishimura, Regular factors of line graphs. II, Math. Japon. 36 (1991) 1033–1040.
[293] T. Nishimura, A degree condition for the existence of k-factors, J. Graph Theory 16 (1992) 141–151.
[294] T. Nishimura, Degree factors of line graphs, Ars Combin. 38 (1994) 149–159.
[295] T. Nishimura, Component factors and induced subgraphs, J. Graph Theory 22 (1996) 305–308.
[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.
[297] T. Nishizeki, On the relationship between the genus and the cardinality of the maximum matchings of a graph, Discrete Math. 25 (1979)
149–156.
[298] J. Orlin, Dynamic matchings and quasi-dynamic fractional matchings I and II, Networks 13 (1983) 551–580.
[299] D. Palumbíny, On a certain type of decompositions of complete graphs into factors with equal diameters, Mat. Časopis Sloven. Akad. Vied
22 (1972) 235–242.
[300] D. Palumbíny, On decompositions of complete graphs into factors with equal diameters, Boll. Un. Mat. Ital. 7 (4) (1973) 420–428.
[301] D. Palumbíny, S. Znám, On decompositions of complete graphs into factors with given radii, Mat. Časopis Sloven. Akad. Vied 23 (1973)
306–316.
[302] L. Perkovic, B. Reed, Edge coloring regular graphs of high degree, Discrete Math. 165/166 (1997) 567–578.
[303] B. Péroche, Complexité de l’arboricité linéaire d’un graphe, II., RAIRO Rech. Opér. 19 (1985) 293–300.
[304] J. Petersen, Die Theorie der regulären Graphen, Acta Math. 15 (1891) 193–220.
[305] P. Peterson, M. Loui, The general maximum matching algorithm of Micali and Vazirani, Algorithmica 3 (1988) 511–533.
[306] C. Picouleau, Complexity of the hamiltonian cycle in regular graph problem, Theoret. Comput. Sci. 131 (1994) 463–473.
[307] M. Planthold, S. Tipnis, Regular multigraphs of high degree are 1-factorizable, Proc. London Math. Soc. 44 (1991) 393–400.
[308] M. Plantholt, S. Tipnis, All regular multigraphs of even order and high degree are 1-factorable, Electron. J. Combin. 8 (2001) #R41.
[309] J. Plesník, Complexity of decomposing graphs into factors with given diameters or radii, Math. Slovaca 32 (1982) 379–388.
[310] J. Plesník, A note on the complexity of finding regular subgraphs, Discrete Math. 49 (1984) 161–167.
[311] M. Plummer, Extending matchings in graphs: a survey, Discrete Math. 127 (1994) 277–292.
[312] M. Plummer, Extending matchings in graphs: an update, Congr. Numer. 116 (1996) 3–32.
[313] K. Podewski, K. Steffens, Injective choice functions for countable families, J. Combin. Theory Ser. B 21 (1976) 40–46.
[314] W. Pulleyblank, Fractional matchings and the Edmonds–Gallai theorem, Discrete Appl. Math. 16 (1987) 51–58.
[315] W. Pulleyblank, Matchings and Extensions, Handbook of Combinatorics, Elsevier, Amsterdam, 1995 pp. 179–232.
[316] S. Quinn, Isomorphic factorizations of complete equipartite graphs, J. Graph Theory 7 (1983) 285–310.
[317] R. Rado, Factorization of even graphs, Quart. J. Math. Oxford Ser. 20 (1949) 94–104.
[318] R. Rizzi, Finding 1-factors in bipartite regular graphs and edge-coloring bipartite graphs, SIAM J. Discrete Math. 15 (2002) 283–288.
[319] H. Robalewska, 2-factors in random regular graphs, J. Graph Theory 23 (1996) 215–224.
[320] A. Robertshaw, k-factors and extendability in bipartite graphs, preprint, November, 2002.
[321] C. Rodger, Graph decompositions, Matematiche (Catania) 45 (1990) 119–139.
[322] A. Ruciński, Subgraphs of random graphs: a general approach, Random Graphs ’83 (Poznań, 1983), North-Holland Mathematical Studies,
vol. 118, North-Holland, Amsterdam, 1985, pp. 221–229.
[323] Z. Ryjáček, A. Saito, R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109–117.
[324] A. Saito, One-factors and k-factors, Discrete Math. 91 (1991) 323–326.
[325] A. Saito, M. Watanabe, Partitioning graphs into induced stars, Ars Combin. 36 (1993) 3–6.
[326] J. Schönheim, A. Bialostocki, Decomposition of Kn into subgraphs of prescribed type, Arch. Math. (Basel) 31 (1978/79) 105–112.
[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.
[328] A. Schrijver, Bipartite edge colouring in O(m) time, SIAM J. Comput. 28 (1998) 841–846.
[329] A. Schrijver, Counting 1-factors in regular bipartite graphs, J. Combin. Theory Ser. B 72 (1998) 122–135.
[330] A. Schrijver, W. Valiant, On lower bounds for permanents, Nederl. Akad. Wetensch. Indag. Math. 42 (1980) 425–427.
[331] E. Shamir, E. Upfal, On factors in random graphs, Israel J. Math. 39 (1981) 296–302.
[332] E. Shamir, E. Upfal, One-factor in random graphs based on vertex choice, Discrete Math. 41 (1982) 281–286.
[333] R. Stanton, I. Goulden, Graph factorization, general triple systems, and cyclic triple systems, Aequationes Math. 22 (1981) 1–28.
[334] K. Steffens, Matchings in countable graphs, Canad. J. Math. 29 (1977) 165–168.
[335] K. Steffens, Maximal tight sets and the Edmonds–Gallai decomposition for matchings, Combinatorica 5 (1985) 359–365.
[336] K. Steffens, Faktoren in unendlichen Graphen, Jahresber. Deutsch. Math.-Verein. 87 (1985) 127–137.
[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] D. Sumner, 1-factors and anti-factor sets, J. London Math. Soc. 13 (1976) 351–359.
[341] V. Tashkinov, 3-regular subgraphs of 4-regular graphs (Russian), Mat. Zametki 36 (1984) 239–259 English transl.: Math. Notes 6 (1984)
612–623.
[342] C. Thomassen, A remark on the factor theorems of Lovász and Tutte, J. Graph Theory 5 (1981) 441–442.
[343] C. Thomassen, Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory 7 (1983) 165–167.
[344] T. Tokuda, A degree condition for the existence of [a, b]-factors in K1,n -free graphs, Tokyo J. Math. 21 (1998) 377–380.
[345] N. Tokushige, Binding number and minimum degree for k-factors, J. Graph Theory 13 (1989) 607–617.
[346] E. Tomová, Decomposition of complete bipartite graphs into factors with given radii, Math. Slovaca 27 (1977) 231–237.
[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] E. Tomová, Decomposition of complete bipartite graphs into factors with given diameters and radii, Math. Slovaca 34 (1984) 249–253.
[349] J. Topp, P. Vestergaard, Odd factors of a graph, Graphs Combin. 9 (1993) 371–381.
[350] M. Truszczynski, Linear arboricity of graphs, Math. Slovaca 36 (1986) 105–108.
[351] W. Tutte, The factorization of linear graphs, J. London Math. Soc. 22 (1947) 107–111.
[352] W. Tutte, The factors of graphs, Canad. J. Math. 4 (1952) 314–328.
[353] W. Tutte, A short proof of the factor theorem for finite graphs, Canad. J. Math. 6 (1954) 347–352.
[354] W. Tutte, On the problem of decomposing a graph into n connected factors, J. London Math. Soc. 36 (1961) 221–230.
[355] W. Tutte, Spanning subgraphs with specified valencies, Discrete Math. 9 (1974) 97–108.
[356] W. Tutte, Graph factors, Combinatorica 1 (1981) 79–97.
[357] J. Uhry, Sur le probléme du couplage maximal, RAIRO 9 (1975), V-3, 13–20.
[358] L. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979) 189–201.
[359] L. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8 (1979) 410–421.
[360] B. van der Waerden, Problem 45, Jahresber. Deutsch. Math.-Verein. 35 (1926) 117. √
[361] V. Vazirani, A theory of alternating paths and blossoms for proving correctness of the O( V E) general graph maximum matching algorithm,
Combinatorica 14 (1994) 71–109.
[362] L. Volkmann, Regular graphs, regular factors, and the impact of Petersen’s theorems, Jahresber. Deutsch. Math.-Verein. 97 (1995) 19–42.
[363] W. Wallis, One-factorizations, Kluwer Academic Publishers Group, Dordrecht, 1997.
[364] J. Wang, Isomorphic factorizations of complete equipartite graphs–the proof of the Harary–Robinson–Wormald conjecture, Sci. Sinica Ser.
A 25 (1982) 1152–1164.
[365] D. Woodall, k-factors and neighbourhoods of independent sets in graphs, J. London Math. Soc. 41 (1990) 385–392.
[366] N. Wormald, Isomorphic factorizations. VII. Regular graphs and tournaments, J. Graph Theory 8 (1984) 117–122.
[367] J.-L. Wu, On the linear arboricity of planar graphs, J. Graph Theory 31 (1999) 129–134.
[368] B. Xu, Z. Liu, T. Tokuda, Connected factors in K1,n -free graphs containing a (g, f )-factor, Graphs Combin. 14 (1998) 393–395.
[369] G. Yan, Some new results on (g, f )-factorizations of graphs, J. Combin. Math. Combin. Comput. 18 (1995) 177–185.
[370] G. Yan, Some new results on (g, f )-factorizations of graphs, Math. Appl. (Wuhan) 9 (1996) 117–120 (in Chinese).
[371] G. Yan, J. Pan, C. Wong, T. Takuda, Decompositions of graphs into (g, f )-factors, Graphs Combin. 16 (2000) 117–126.
[372] J. Yang, Y. Ma, G. Liu, Fractional (g, f ) factors of graphs, Appl. Math. J. Chinese Univ. Ser. A 16 (2001) 385–390.
[373] Q. Yu, On barrier sets of star-factors, Graphs Combin. 6 (1990) 71–76.
[374] Q. Yu, On star-factor covered graphs, J. Math. (Wuhan) 11 (1991) 450–454.
[375] Q. Yu, Counting the number of star-factors in graphs, J. Combin. Math. Combin. Comput. 23 (1997) 65–76.
[376] C.-Q. Zhang, Y. Zhu, Factorizations of regular graphs, J. Combin. Theory Ser. B 56 (1992) 74–89.
[377] L. Zhang, Every 4-regular simple graph contains a 3-regular subgraph, J. Changsha Railway Inst. 1 (1985) 130–154.
[378] L. Zhang, G. Liu, Fractional k-factors of graphs, J. Systems Sci. Math. Sci. 21 (2001) 88–92 (in Chinese).
[379] S. Znám, On a conjecture of Bollobás and Bosák, J. Graph Theory 6 (1982) 139–146.

Plummer F Factor Survey

Uploaded by

Copyright:

Available Formats

Plummer F Factor Survey

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Plummer F Factor Survey

Uploaded by

Copyright:

Available Formats

Discrete Mathematics 307 (2007) 791 – 821

Dedicated to the memory of Peter Owens

Keywords: Factor; Factorization; Matching

A subgraph H of a graph (multigraph, general graph) G, is a factor of G if H is a spanning subgraph of G. This

E-mail address: [email protected].

Petersen’s result was later generalized by Bäbler as follows:

Sumner extended this result as follows.

The binding number of G, denoted bind (G), is deﬁned to be

then G has a 1-factor.

Theorem 2.12. Let G be connected and have a unique 1-factor. Then:

(a) G has a cutedge belonging to the 1-factor;

Theorem 2.13. If G is k-connected and has a 1-factor, then either

Theorem 2.14. If G is bicritical, then (G) |V (G)|/2 + 1.

From the two preceding facts one has the following.

(a) |A| = |B| and

Theorem 2.18. If G is bipartite, then (G) =

Theorem 2.20. Let G be a simple k-regular bipartite graph on 2n vertices. Then

2.2. (g, f )-factors

2.3. [a, b]-factors

(ii) i(G − S)n|S|, for all S ⊆ V (G) and

If f is a function from V (G) to the positive integers such that

(iii) x∈V (G) f (x) is even and

then G has an f-factor.

Theorem 2.44. If tough (G) k, then G has an k-factor.

(Katerinis [203] later generalized this result to one about f-factors.)

(G) max{k(k + 2)/2, (k + 2)(G)/4},

then G has an k-factor.

(See also [201,286].)

(See also [323,47] and [57].)

(See [101] for a generalization of the above result.)

A sufﬁcient condition for a k-factor in the line graph is given next.

A sample result on the existence of k-factors in bipartite graphs is the following.

A recent interesting generalization of the above result may be found in [28].

2.6. Connected factors

(See also [258,259].)

(See also [93] and [281].)

(i) G has a path factor,

Theorem 3.1. (a) Every 3-regular graph has a {P3 , P4 , P5 }-factor.

For claw-free graphs, one has the next result.

(See also Section 2.3 above.)

(Here a Sr -factor is proper if it has at least one component isomorphic to K1,r ).

(The reader is also referred to [96,98].)

4. Factors in random graphs

See also [51].

Another approach to the conjecture is represented by the following result.

5.2. [a, b]-factorizations

(See also [257] and [13].)

(i) G has an ([r, r + 1]-factorization with exactly x [r, r + 1]-factors if

Corollary 5.10 (Era [102], Egawa [78]). Let k 2 be an integer. Then:

5.3. Linear arboricity

Theorem 5.11 (Akiyama et al. [10]). If G is any graph, a(G) 3/2/2.

5.4. Factorizations of complete graphs

6. Factor algorithms and complexity

A set S (respectively, Sn ) of stars is said to be sequential if S = {K1,1 , K1,2 , K1,3 , . . .} (respectively Sn =

Theorem 6.5 (König [216,217]). If G is bipartite, then  (G) = (G).

Conjecture 6.10. The problems of

The author proves the conjecture true in various special cases.

Thus, by Vizing’s theorem, we have the next result.

Theorem 6.13. If G is r-regular and t r + 1, then G is t-rational.

(G) max{k(k + 2)/2, (k + 2)(G)/4},

Theorem 5.11 (Akiyama et al. [10]). If G is any graph, a(G) 3/2/2.

Theorem 6.5 (König [216,217]). If G is bipartite, then (G) = (G).