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₈=deg₆ (v₈) for all vertices \v₁, , v₍\ of G, we call m () =\i|d₈ i\ the strong index of. For k 0, we can show that for every c ₋ ₌ () \₋+₋{2\}+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₍+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.
James M. Shook (Fri,) studied this question.