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.

Kolmogorov-Arnold Networks, Chromatic Index, Cubic Graphs, Classification, Data Analysis

1. P.Z. de Silva et al. Interference graph dataset for machine learning-based register allocation. IEEE Access, 2024.

2. A. Dudáš and B. Modrovičová. Decision trees in proper edge k-coloring of cubic graphs. In Proceedings of Conference of Open Innovation Association, FRUCT. 2023.

3. A. Dudáš and B. Modrovičová. Determining chromatic index of cubic graph with the use of explainable classifiers: A comparative study. Journal of Applied Mathematics, Statistics and Informatics, 2024.

4. A. Dudáš and B. Modrovičová. Interpretable random forest model for identification of edge 3- uncolorable cubic graphs. Kybernetika, 2024.

5. A. Michalikova et al. Can wood-decaying urban macrofungi be identified by using fuzzy interference system? an example in central european ganoderma species. Scientific Reports, 2021.

6. A.A. Jones et al. Graph filter. Zenodo, 2023.

7. G. Jayabalasamy et al. Application of graph theory for blockchain technologies. Mathematics, 2024.

8. J. Ondriga et al. Generation of bicycle frame image designs using dcgan network. 2023.

9. K. Coolsaet et al. House of graphs 2.0: A database of interesting graphs and more. Discrete Applied Mathematics, 2023.

10. M. Kvet et al. Concept of temporal data retrieval: Undefined value management. Concurrency Computation - Practice and Experience, 2020.

...