A graph homomorphism is a function between the vertex set of two graphs which maps pairs of adjacent vertices to pairs of adjacent vertices. Many graph parameters can be expressed in terms of finding a homomorphism that maximizes or minimizes a certain objective function: the chromatic number , the clique number , and the Lovász function are noteworthy examples. This work studies graph homomorphisms optimization using combinatorial and convex optimization. Grounded on the theory of preordered sets, we develop a framework that captures a combinatorial duality between the clique and coloring numbers, and that formulates several graph parameters in the literature. We demonstrate known results on convex corners and antiblockers, and we use these geometric concepts to explain some properties of the graph parameters of interest. In particular, we present a geometric duality between upper bounds for the stability number of a graph and lower bounds for the fractional chromatic number of a graph. We use this duality to provide a new understanding of the relationship between two famous spectral bounds introduced by Hoffman. Building on the concepts previously presented, we study convex corners and generalizations of graph homomorphisms which use cones of symmetric matrices. We relate the Choi representation of linear transformations with conic formulations of graph homomorphisms, thus uncovering a new connection between ideas from quantum information theory. Several results and concepts are approached in distinct ways throughout the text, establishing with theorems and examples the cohesion between the combinatorial and geometric perspectives.

Um homomorfismo de grafos é uma função entre os vértices de dois grafos que mapeia pares de vértices adjacentes em pares de vértices adjacentes. Diversos parâmetros de grafos podem ser formulados em termos de encontrar um homomorfismo que maximize ou minimize um certo valor objetivo: o número cromático , o número de clique e a função de Lovász são exemplos notáveis. Este trabalho estuda otimização de homomorfismos de grafos utilizando otimização convexa e combinatória. Apresentamos um arcabouço, fundamentado na teoria de conjuntos pré-ordenados, que evidencia uma dualidade combinatória entre o número de clique e o número cromático, além de ser capaz de formular diversos parâmetros na literatura. Demonstramos resultados conhecidos sobre cantos convexos e anti-bloqueadores, e então utilizamos esses conceitos geométricos para explicar certas propriedades de alguns dos parâmetros que nos interessam. Em particular, descrevemos uma dualidade geométrica entre limitantes superiores ao número de estabilidade de um grafo e limitantes inferiores ao número cromático fracionário de um grafo. Utilizamos essa dualidade para fornecer um novo entendimento sobre a relação entre dois famosos limitantes espectrais introduzidos por Hoffman. Aproveitando os conceitos previamente discutidos, abordamos diretamente construções que definem cantos convexos e generalizações de homomorfismos a partir de cones de matrizes simétricas. Relacionamos a representação de Choi de uma transformação linear às formulações cônicas de homomorfismos, obtendo assim uma nova conexão entre ideias presentes na teoria quântica da informação. Diversos resultados e conceitos são apresentados de distintas maneiras no decorrer do texto, estabelecendo através de teoremas e exemplos a coesão entre as perspectivas combinatória e geométrica.