Coloração de arestas em grafos cobipartidos

Abstract

The minimization of the number of colors for edge coloring of graphs is a relevant problem in graph theory, with applications in several areas such as communication networks, resource allocation, and optimization. We investigate efficient methods for edge coloring in cobipartite graphs, considering established techniques and structural properties that influence the distribution of colors. The study is justified by the need to better understand the relationship between the structure of these graphs and their coloring, enabling both theoretical and practical advances in the field. To this end, the characteristics of these graphs are analyzed, with emphasis on the organization of vertices into cliques, along with a review of existing algorithms that can be applied or adapted. The methodology involves the formulation of mathematical proofs. As a result, structural properties that impact coloring are identified, as well as adaptations of algorithms for this class of graphs. The systematization of these findings contributes to the development of guidelines that expand the understanding of edge coloring in cobipartite graphs.