Kolmogorov-Arnold Networks in Identification of Chromatic Index of Cubic Graphs

The chromatic index of a graph denotes the number of colors needed for such a coloring of this graph, that no two adjacent edges are colored with the use of the same color. The value of this graph property is commonly used in several real-world problems, such as the determination of the number of time slots for traffic lights placed in the intersection system, or the allocation of registers to variables in the compilation of code. Since the problem of chromatic index identification is NP-complete, the conventional computing methods are of high time complexity. This motivated the recent use of machine and deep learning models for the approximate determination of the value of the graph property. In this study, the Kolmogorov-Arnold Network is designed, implemented, and experimentally evaluated in the context of the selected task. This model has been utilized for its high decision-making quality and strong interpretability, which are both explored in the presented work through conventional classification metrics such as accuracy and precision and through means of visualization and symbolic approach to the interpretation of the decisionmaking process.