Determining chromatic index of cubic graph with the use of explainable classifiers: A comparative study

Proper edge 3-coloring of a cubic graph is an NP-complete problem, which can be used in order to model several interesting practical problems. A method for correct and efficient assigning of variables used in the program to registers of the system, scheduling of a set of tasks to a set of processors while each task has to be executed on a number of processors simultaneously, or frequency assignment of radio stations without interference are all typical instances of problems modelled by graph coloring. When considering cubic graphs, which consist of vertices incident to precisely three edges, we can identify two distinct graph groups divided by their chromatic index, a minimal number of colors needed for the proper coloring of such graph. In the research presented in this article, we conduct a comparative study of the effectiveness of machine learning classifiers in the task of determining the chromatic index of cubic graphs, present an evaluation of the accuracy and precision of these models, and use the Shapley Additive Explanations model for the identification of graph attributes and their values crucial in the models’ decision making.