Equitable factorizations of highly edge-connected graphs: complete characterizations

In this paper, we show that every highly edge-connected graph G, under a necessary and sufficient degree condition, can be edge-decomposed into k factors G₁, , Gₖ such that for each vertex v V (Gᵢ) with 1 i k, |d₆㶁 (v) -dG (v) /k|<1. This characterization covers graphs having at least k-1 vertices with degree not divisible by k. In addition, we investigate almost equitable factorizations in arbitrary edge-connected graphs. Next, we establish a simpler criterion for the existence of factorizations G₁, , Gₖ satisfying d₆㶁 (v) dG (v) /k for all vertices v (reps. d₆㶁 (v) dG (v) /k). As an application, we come up with a criterion to determine whether a highly edge-connected graph with (G) ₁++ ₘ (resp. (G) ₁++ ₘ) can be edge-decomposed into factors G₁, , Gₘ satisfying (Gᵢ) ᵢ (resp. (Gᵢ) ᵢ) for all i with 1 i m, provided that ₁++ ₘ is divisible by an odd number p and ᵢ p-1 2 (resp. ₁++ ₘ is divisible by p and ᵢ p-1 2). For graphs of even order, we replace an odd-edge-connectivity condition. In particular, for the special case m=2, we refine the needed odd-edge-connectivity further by giving a sufficient odd-edge-connectivity condition for a graph G to have a partial parity factor F such that for each vertex v with a given parity constraint, | d₅ (v) - dG (v) |< 2, and for all other vertices v, | d₅ (v) - dG (v) | 1, where is a real number and 0< < 1. Finally we introduce another application on the existence of almost even factorizations of odd-edge-connected graphs.