Dans ce travail, nous étudions l'apport de la méthode de recherche arborescente Monte-Carlo (MCTS) combinée à des heuristiques dédiées à la résolution du problème de coloration pondéré. A partir de l'algorithme MCTS de base, nous introduisons progressivement un certain nombre de variantes algorithmiques de façon à améliorer la phase de simulation du MCTS pour ce problème particulier, notamment avec des algorithmes gloutons et une heuristique de recherche locale. Ces différentes variantes sont évaluées sur des instances de référence de la littérature et les résultats empiriques obtenus sont comparés afin de mettre en lumière les avantages et les limites de chaque stratégie.