L'algorithme RLF (Recursive Largest First) est l'un des plus populaires parmi les heuristiques gloutonnes pour le problème de la coloration des sommets d'un graphe. Il construit séquentiellement des classes de couleur sur la base de choix gloutons. En particulier, le premier sommet à être introduit dans une classe \(C\) est choisi parmi ceux ayant un nombre maximum de voisins non colorés, et les prochains sommets rajoutés à \(C\) sont ceux ayant un nombre maximum de voisins non colorés qui ne peuvent plus faire partie de la classe \(C\). Ces choix gloutons peuvent avoir un impact considérable sur la performance de l'algorithme, ce qui justifie notre proposition de règles alternatives. Des expériences réalisées sur 63 exemples difficiles de la banque de données DIMACS démontrent que le nouvel algorithme de type RLF, lorsque comparé à l'algorithme original, permet d'obtenir une réduction de plus de 50% de l'écart entre le nombre de couleurs utilisées et la meilleure borne supérieure connue sur le nombre chromatique. Le nouvel algorithme glouton se montre même compétitif avec des métaheuristiques de base pour le problème de la coloration des sommets d'un graphe.