Coloração harmônica de grafos: uma abordagem utilizando programação inteira

Abstract

For many researchers the graphs coloring problems are the most popular subject in Graph Theory. This popularity is given by the fact of those problems being widely used in uncounted problem in the real life. Amoung its variations lies the Harmonic Coloring of Graphs Problem (HCGP), whose object is find the lower number of colors able to color the vertices of graph, allowed adjacents vertices share the same color, and making the edges distinguishable by the color set associated with their vertices. Currently it’s not find in the literature an exact form to solve the HCGP. In counterpoint the present work introduce the development of integer linear programming models, based in the set colors and vertices representatives, to auxiliate in resolution of HCGP for various types of instances. It also presented valid inequalities for each mathematical model, also too, a mathematical study about the polyedra associated to the problem. For the observed intances, the model present a good performance and showing up efficient to use in real problems.