Um algoritmo de recoloração de arestas de grafos

Abstract

The problem to find the minimum of colors that are necessary to color all edges on a graph G, known as Classification Problem, is an NP-complete problem. As stated by the Vizing’s Theorem, we have only two classes for all graphs, that is, the chromatic index of G (the minimum number of colours needed to colour the edges of G) is either ∆, in that case G is Class 1, or ∆ +1, in that case G is Class 2. For some graph classes some polynomial algorithms had been found to determine its chromatic index. This workshowsastudyonapolynomialtimerecolouringproceduretoconstructa ∆-edgecolouring of graphs which belong to the class X , that is, the class of graphs whose majors (vertices of degree ∆) have local degree sum (the local degree sum of some vertex u is the sum of the degrees of all neighbors of u) at most ∆2 − ∆. We conclude showing some ideas for future works which consist of an extension of the class X .