Resultados teóricos e computacionais sobre coloração harmoniosa de grafos

Abstract

Given a graph G, a proper vertex k-coloring is a function c : V(G) → {1,..., k} such that adjacent vertices cannot receive the same color. A vertex coloring of a graph G is harmonic when each of the color pairs induces at most one edge, that is, the subgraph induced in the vertices with those colors has at most one edge. If the coloring is harmonic and proper, we say that this coloring is a harmonious coloring. The coloring problems that we study here are problems that the main interest is to minimize the number of colors used in a harmonious coloring of a given graph G. In this master thesis, we present a survey of the harmonic and the harmonious coloring problems. The harmonic coloring problem, the one without the restriction of proper coloring, has been little studied until nowadays. We mention in our survey the only work in the literature that present integer linear programming models for the harmonic coloring problem. Regarding harmonious coloring, we present in addition to the survey, as a new result a relation on the harmonious chromatic numbers of a pair of graphs (G,H), such that H is obtained by the identification of vertices of G that have distance at least three. Furthermore, we corrected a bound in the literature for the harmonious chromatic number of d-degenerate graphs. We propose three integer linear programming models and two greedy heuristics. We present tables with tests about these formulations and heuristics on random instances. Moreover, we did a study on the dimension of the polytopes associated to two of the three mentioned models.