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, |dGᵢ(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 dGᵢ(v)≥ dG(v)/k for all vertices v (reps. dGᵢ(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, | dF(v)-ε dG(v)|< 2, and for all other vertices v, | dF(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.