The graph coloring problem is a well-known NP-Complete problem for which many algorithms have been developed along the last decades. Because of the difficult nature of this problem, the idea of algorithm selection becomes relevant so that one can run only the most appropriate coloring algorithm. This work presents a systematic analysis of the application of machine learning methods to the algorithm selection problem using graph coloring as a case study. Much work has been done in this topic focusing on single label classification and instance space visualization, leaving sideways other methods such as regression and multi-label classification. Furthermore, no systematic approach has been adopted to test changes on the list of graph features available as input. These gaps are addressed throughout a series of experiments using as a starting point datasets and feature sets considered on previous related works. The results show that the methods employed in this work can provide good results in terms of accuracy when selecting the best coloring algorithms. It was also clear that the accuracy of the learning algorithms is highly dependent on the performance criteria and can be impacted by the graph features. The idea of multi-label classification in this context brings great improvement as after some time, some coloring algorithms seem to reach similar values for the chromatic number. In the end, from a portfolio of eight algorithms, it was possible to recommend on average just four of those with an accuracy of 89% or only one with an accuracy of 79%

Full Text available here