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 $k$ is called a $k$-factor; a $1$-factor is also called a perfect matching. A graph is called $k$-factorizable (or $k$-factorable) if it can be represented as a union of edge-disjoint $k$-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 $1$-factorizable. A connected graph is $2$-factorizable if and only if it is a regular graph of even degree. A graph $G$ has a $1$-factor if and only if it has an even number of vertices and if there is no subset of vertices $U$ such that the number of components with an odd number of vertices of the graph $G\setminus U$, obtained from $G$ by deleting the vertices of $U$, exceeds $|U|$. Every two-connected regular graph of degree 3 can be decomposed into a $1$-factor and a $2$-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 $G$ is equal to

$$\max_k=\left\lbrace\frac{g_k}{k-1}\right\rbrace,$$

where $g_k$ is the largest number of edges in the $k$-vertex subgraphs of $G$.

References

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

Comments

A spanning subgraph of a graph $G=(V,E)$ is a subgraph $G_1=(V_1,E_1)$ whose set of vertices $V_1$ is equal to the set of vertices $V$ of $G$.

The $1$-factor theorem quoted above is due to W.T. Tutte. Given a vertex function $f$, a factor $F$ is called an $f$-factor if $d(v|F)=f(x)$ for every $v\in V$, the vertex set of $G$. Tutte also proved an $f$-factor theorem. The results on $2$-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