Let $G$ be a claw-free graph. Prove that if $G$ has a proper coloring of exactly $k$ colors, then $G$ has a proper $k$-coloring where the cardinality of the color classes differ by at most $1$. I'm not looking for a complete solution since this is part of an assignment I have to hand in to my teacher but I would appreciate some tips regarding how to go about proving this and I will attempt to fill in the gaps myself.
I've attempted to prove this by induction on $k$. Clearly it is true for $k=1$. I then assume that it is true for $k = n-1$, $n\geq2$. Finally I consider the case $k=n$. I let $C_1,...,C_k$ be the color classes of a $k$-coloring of $G$. I can without a loss of generality stipulate that $C_k$ has the smallest cardinality of all the aforementioned classes. I then study $G-C_k$, it must be claw-free as well and has a $(k-1)$-coloring with classes $C_1,...,C_{k-1}$ so we can use the inductive hypothesis. I let the $\hat{C}_1,...,\hat{C}_{k-1}$ be classes for which one has cardinality $C$ and possibly some class has cardinality $C+1$. So I have a $k$-coloring of $G$ which is $\hat{C}_1,...,\hat{C}_{k-1},C_k$. I've been able to show $\mid C_k \mid\leq C$ but I suspect that I will be unable to show that $\mid C_k \mid\geq C$ as well since I don't see why that would have to be the case. Thus I'm pretty much left with nothing. How do I go about proving this? In particular, how do I make use of the fact that the graph is claw-free to prove this?
Let $C_1,...,C_k$ be the color classes of a $k$-coloring of $G$. Denote by $G_{i,j}$ the bipartite graph induced by $C_i$ and $C_j$ for $1 \le i, j \le k$. Then $\Delta(G_{i,j}) \le 2$ since $G$ is a claw-free. So, $G_{i,j}$ is the union of even cycles and paths which could be colored with two colors where the cardinality of the color classes differ by at most $1$.
The above observation allows the re-coloring of $G$ to have a coloring with the desired property.