Connected equitably Δ-colorable realizations with k-factors

A graph G is said to be equitably c-colorable if its vertices can be partitioned into c independent sets that pairwise differ in size by at most one. Chen, Lih, and Wu conjectured that every connected graph G with maximum degree Δ(G)≥ 2 has an equitable coloring with Δ(G) colors, except when G is complete, an odd cycle, or a balanced bipartite graph with odd sized partitions. Suppose G is a connected graph with a k-factor (a regular spanning subgraph) F such that G is not complete, a $1$-factor, nor an odd cycle. When k≥ 1 we demonstrate that there is a connected $(k-1)$ edge-connected equitably Δ(G)-colorable graph H with a k-factor $F'$ such that $G-E(F)=H-E(F')$. If we drop the requirement that $G-E(F)=H-E(F')$, then we can say more. Considering the non-increasing degree sequence π=(d₁,…, dₙ) of G where dᵢ=degG(vᵢ) for all vertices ₁,…,vₙ\ of G, we call m(π)=max|dᵢ≥ i\ the strong index of π. For k≥ 0, we can show that for every c≥ maxl≤ m(π)ₗ+l2\+1 we can find a connected $(k-1)$ edge-connected equitably c-colorable realization H of π that has a k-factor. In a third theorem we show that if d_d₁-dₙ+1≥ d₁-dₙ+k-1, then some realization of π has a k-factor. Together, these three theorems allow us to prove that for all k, there is a connected equitably Δ(G)-colorable realization H of π with a k-factor. Thus, giving support to the validity of the Chen-Lih-Wu Conjecture.