The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs. / O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, os graus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos.

Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G, there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (Mink-CDS). We prove that Mink-CDS is NP-hard on planar bipartite graphs of maximum degree 4. We also prove that Mink-CDS is APX-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for Mink-CDS on bipar- tite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complex- ity of computing this graph parameter. On the positive side, we show an approximation algorithm for Mink-CDS. When k = 1, we present two new approximation algorithms for the weighted version of the problem, one of them restricted to graphs with a poly- nomially bounded number of minimal separators. Finally, also for the weighted variant of the problem where k = 1, we discuss an integer linear programming formulation and conduct a polyhedral study of its associated polytope. / Seja G um grafo conexo e k um inteiro positivo. Um subconjunto D de vértices de G é um conjunto dominante conexo de k-saltos se o subgrafo de G induzido por D é conexo e se, para todo vértice v em G, existe um vértice u em D a uma distância não maior do que k de v. Estudamos neste trabalho o problema de se encontrar um conjunto dominante conexo de k-saltos com cardinalidade mínima (Mink-CDS). Provamos que Mink-CDS é NP-difícil em grafos planares bipartidos com grau máximo 4. Mostramos que Mink-CDS é APX-completo em grafos bipartidos com grau máximo 4. Apresentamos limiares de inaproximabilidade para Mink-CDS para grafos bipartidos e (1, 2)-split, sendo que um desses é expresso em função de um parâmetro independente da ordem do grafo. Também discutimos a complexidade computacional do problema de se computar tal parâmetro. No lado positivo, propomos um algoritmo de aproximação para Mink-CDS cuja razão de aproximação é melhor do que a que se conhecia para esse problema. Finalmente, quando k = 1, apresentamos dois novos algoritmos de aproximação para a versão do problema com pesos nos vértices, sendo que um deles restrito a classes de grafos com um número polinomial de separadores minimais. Além disso, discutimos uma formulação de programação linear inteira para essa versão do problema e provamos resultados poliédricos a respeito de algumas das desigualdades que constituem o politopo associado à formulação.

Conselho Nacional de Desenvolvimento Científico e Tecnológico / This study shows the influence of the molecular topology of the crystal of a series of 14 pyrazolo[1,5-a]pyrimidines. The topological data were obtained from X-ray diffraction data and energy stabilization were determined by thermal analysis and chemical computations. Topological analysis carried out was Molecular Coordination Number (NCM) using the Voronoi-Dirichlet polyhedra and Hirshfeld surface. The NCM found for the majority of compounds was 14. Furthermore, it was determined contact area and the solid angle between molecules of the first coordination sphere of the cluster. Several correlations between data were performed, where it is possible highlight the correlation between the area of contact of the cluster molecules and the interaction energy and the solid angle and interaction energy were established. These correlations showed that there is a proportionality between the data, showing that the greater the contact area, the greater the interaction energy for a series of pyrazolo[1,5-a]pyrimidine studied in this thesis. As the contact area, solid angle also presents proportionality with the calculated interaction energy. Among the atom-atom contacts present on the surface of the test compounds was observed that contacts C∙∙∙H and C∙∙∙C are key to stabilize the crystals. This result corroborates the hypothesis that the contact surface between the molecules would be the driving force for the crystalline arrangement. / Este trabalho apresenta o estudo da influência da topologia molecular na organização cristalina de uma série de 14 pirazolo[1,5-a]pirimidinas. Os dados topológicos foram obtidos por difratometria de raios-X e os dados de energia de estabilização foram determinados por análises térmicas e cálculos computacionais. Dentre as análises topológicas realizadas destaca-se a determinação do Número de Coordenação Molecular (NCM) usando o Poliedro de Voronoi-Dirichlet e a Superfície de Hirshfeld. O NMC encontrado para a maioria dos compostos foi de 14. Além disso, foi determinada a área de contato, bem como o ângulo sólido entre as moléculas da primeira esfera de coordenação do cluster. Estabeleceu-se uma serie de correlações entre os dados obtidos, entre elas, destaca-se a correlação entre esta área de contato entre as moléculas do cluster e a energia de interação, bem como a correlação ângulo sólido e energia de interação. Ambas correlações mostraram que há uma proporcionalidade entre os dados, mostrando que quanto maior a área de contato, maior a energia de interação para a série de pirazolo[1,5-a]pirimidinas estudadas nesta dissertação. Assim como a área de contato, o ângulo sólido também apresenta uma proporcionalidade com a energia de interação calculada. Dentre os contatos átomo-átomo presentes na superfície dos compostos em estudo, observou-se que os contatos C∙∙∙H e C∙∙∙C são os principais para a estabilização dos cristais estudados. Este resultado corrobora com a hipótese de que a superfície de contato entre as moléculas seria a força motriz para o arranjo cristalino.