Graph Coloring and Graph Convexity

Nesta tese, estudamos vÃrios problemas de teoria dos grafos relativos à coloraÃÃo e convexidade em grafos. A maioria dos resultados contidos aqui sÃo ligados à complexidade computacional destes problemas para classes de grafos particulares. Na primeira, e principal, parte desta tese, discutimos coloraÃÃo de grafos que à uma das Ãreas mais importantes de teoria dos grafos. Primeiro, consideramos trÃs problemas de coloraÃÃo chamados coloraÃÃo gulosa, coloraÃÃo ponderada e coloraÃÃo ponderada imprÃpria. Em seguida, discutimos um problema de decisÃo, chamado boa rotulagem de arestas, cuja definiÃÃo foi motivada pelo problema de atribuiÃÃo de frequÃncias em redes Ãticas. A segunda parte desta tese à dedicada a um parÃmetro de otimizaÃÃo em grafos chamado de nÃmero de fecho (geodÃtico). A definiÃÃo deste parÃmetro à motivada pela extensÃo das noÃÃes de conjuntos e fecho convexos no espaÃo Euclidiano. Por m, apresentamos em anexo outros trabalhos desenvolvidos durante esta tese, um em hipergrafos dirigidos Eulerianos e Hamiltonianos e outro sobre sistemas de armazenamento distribuÃdo.In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labeling, whose definition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The definition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems