Arboricity Of Graphs

ARBORICITY: Any graph G can be expressed as a sum of spanning forests, simply by letting each factor contain only one of the q lines of G. A natural problem is to determine the minimum number of line-disjoint spanning forests into which G can be decomposed. This number is called the arboricity of G and is denoted by r (G).

For example. r (K4) = 2 and r (K5) = 3, minimal decompositions of those graphs into spanning forests are shown in Figure 7.6 below.

Theorem . For any nontrivial connected graph G,
α0 β0 = P = α1 β1

Proof. Let M0 be any maximum independent set of points, so that |M0| = β0. Since no line joins two points of M0, the remaining set of P – β0 points constitutes a point cover for G so that α0 ≤ P – β0.
On the other hand, if N0 is a minimum point cover for G, so the set V – N0 is independent. Hence, β0 ≥ P – α0, proving the first equation.
To obtain the second equality, we begin with an independent set M1 of β1 lines.
A line cover Y is then produced by taking the union of M1 and a set of lines one incident line for each point of G not covered by any line in M1.
Since |M1| |Y| ≤ P and |Y| ≥ α1. It follows that α1 β1 ≤ P.
In order to show the inequality in the other direction, let us consider a minimum line cover N1 of G.
Clearly, N1 cannot contain a line both of whose endpoints are incident with lines also in N1.
This implies that N1 is the sum of stars of G (considered as sets of lines).
If one line is selected from each of these stars, we obtain an independent set W of lines.
Now, |N1| |W| = P and |W| ≤ β1.
Thus, ∝1 β1 ≥ P, completing the proof of the theorem. Corollary If P is an hereditary property of G, then
α0 (P) β0 (P) = P.