Factorization

in graph theory

The decomposition of a graph into edge-disjoint spanning subgraphs of a special form. In the general case a factor is a spanning subgraph with a given property. An example of such a property is regularity. A regular spanning subgraph of degree is called a -factor; a -factor is also called a perfect matching. A graph is called -factorizable (or -factorable) if it can be represented as a union of edge-disjoint -factors.

In graph theory one considers questions on the existence of factors of one type or another in an arbitrary graph, on the number of factors, and on the possibility of a factorization of a given type for different classes of graphs. It is known, for example, that a complete graph with an even number of vertices and a complete bipartite graph (cf. Graph, bipartite) with the same number of vertices in each part are -factorizable. A connected graph is -factorizable if and only if it is a regular graph of even degree. A graph has a -factor if and only if it has an even number of vertices and if there is no subset of vertices such that the number of components with an odd number of vertices of the graph , obtained from by deleting the vertices of , exceeds . Every two-connected regular graph of degree 3 can be decomposed into a -factor and a -factor which are edge-disjoint.

Examples of non-regular factors are spanning trees (cf. Tree) and forests, spanning planar subgraphs (see Graph imbedding), etc. Connected with the decomposition of a graph into spanning forests is the numerical characteristic called the arboricity; this is the least number of edge-disjoint spanning forests whose union is the graph. The arboricity of an arbitrary graph is equal to

where is the largest number of edges in the -vertex subgraphs of .

References

[1]	F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9

Comments

A spanning subgraph of a graph is a subgraph whose set of vertices is equal to the set of vertices of .

The -factor theorem quoted above is due to W.T. Tutte. Given a vertex function , a factor is called an -factor if for every , the vertex set of . Tutte also proved an -factor theorem. The results on -factors mentioned above are due to J. Petersen [a1]. A comprehensive treatment of all these results is given by Tutte in [a2]. A recent survey is [a3].

References

[a1]	J. Petersen, "Die theorie der regulären Graphen" Acta. Math. , 15 (1891) pp. 193–220
[a2]	W.T. Tutte, "Graph factors" Combinatorica , 1 (1981) pp. 79–97
[a3]	J. Akiyama, M. Kano, "Factors and factorizations of graphs - a survey" J. Graph Theory , 9 (1985) pp. 1–42