IMPLEMENTAÇÃO DE UM SISTEMA WEB PARA VISUALIZAÇÃO DE COLORAÇÃO DE ARESTAS EM GRAFOS DE CAYLEY Hl,p.

Abstract

This final year project addresses the edge coloring problem in the Cayley graph family Hl,p, analyzing algorithmic strategies and implementing an interactive visualization tool. The theoretical and practical approach is based on the fundamental distinction of the parity of the parameter p. For the case where p is even, the structural property of the graph that allows its decomposition into even-length cycles is explored. This enables the application of an alternating cycle coloring algorithm that achieves the optimal chromatic index of ∆ colors with a linear time complexity of O(|E|). When p is odd, the presence of odd cycles makes this approach unfeasible, requiring the use of the Vizing algorithm (implemented as Misra-Gries), which guarantees a proper coloring with at most ∆ + 1 colors, with a complexity of O(|V ||E|). To validate and demonstrate these results, a web application was developed in Python, using the Dash, NetworkX, and Dash Cytoscape libraries. The tool allows for the generation of instances of the Hl,p graph, applies the corresponding coloring algorithm, and visually displays the result, serving as a practical resource for studying the properties of these graphs.