To complement Yuval's answer, the problem is solvable in polynomial-time more generally for block graphs which generalize complete graphs and trees. See the algorithm of Jansen .
On the other hand, the problem (as you probably know) remains NPC for many graphs that are close to being complete in some sense. This includes complete bipartite graphs, complete graphs minus a matching and complete split graphs (see [2, Table 1] for an overview).
 Jansen, Klaus. "Complexity results for the optimum cost chromatic partition problem." Universit¨at Trier, Mathematik/Informatik, Forschungsbericht 96–41 (1996).
 Bonomo, Flavia, Guillermo Durán, and Javier Marenco. "Exploring the complexity boundary between coloring and list-coloring." Annals of Operations Research 169.1 (2009): 3.