Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes. / An oriented graph is a directed graph with no cycle of length at most two. A homomorphism of an oriented graph to another oriented graph is an arc preserving vertex mapping. To push a vertex is to switch the direction of the arcs incident to it. An orientable graph is an equivalence class of oriented graph with respect to the push operation. An orientable graph [−→G] admits a homomorphism to an orientable graph [−→H] if an element of [−→G] admits a homomorphism to an element of [−→H]. A signified graph (G, Σ) is a graph whose edges are assigned either a positive sign or a negative sign, while Σ denotes the set of edges with negative signs assigned to them. A homomorphism of a signified graph to another signified graph is a vertex mapping such that the image of a positive edge is a positive edge and the image of a negative edge is a negative edge. A signed graph [G, Σ] admits a homomorphism to a signed graph [H, Λ] if an element of [G, Σ] admits a homomorphism to an element of [H, Λ]. The oriented chromatic number of an oriented graph −→G is the minimum order of an oriented graph −→H such that −→G admits a homomorphism to −→H. A set R of vertices of an oriented graph −→G is an oriented relative clique if no two vertices of R can have the same image under any homomorphism. The oriented relative clique number of an oriented graph −→G is the maximum order of an oriented relative clique of −→G. An oriented clique or an oclique is an oriented graph whose oriented chromatic number is equal to its order. The oriented absolute clique number of an oriented graph −→G is the maximum order of an oclique contained in −→G as a subgraph. The chromatic number, the relative chromatic number and the absolute chromatic number for orientable graphs, signified graphs and signed graphs are defined similarly. In this thesis we study the chromatic number, the relative clique number and the absolute clique number of the above mentioned four types of graphs. We specifically study these three parameters for the family of outerplanar graphs, of outerplanar graphs with given girth, of planar graphs and of planar graphs with given girth. We also try to investigate the relation between the four types of graphs and prove some results regarding that. In this thesis, we provide tight bounds for the absolute clique number of these families in all these four settings. We provide improved bounds for relative clique numbers for the same. For some of the cases we manage to provide improved bounds for the chromatic number as well. One of the most difficult results that we prove here is that the oriented absolute clique number of the family of planar graphs is at most 15. This result settles a conjecture made by Klostermeyer and MacGillivray in 2003. Using the same technique we manage to prove similar results for orientable planar graphs and signified planar graphs. We also prove that the signed chromatic number of triangle-free planar graphs is at most 25 using the discharging method. This also implies that the signified chromatic number of trianglefree planar graphs is at most 50 improving the previous upper bound. We also study the 2-dipath and oriented L(p, q)-labeling (labeling with a condition for distance one and two) for several families of planar graphs. It was not known if the categorical product of orientable graphs and of signed graphs exists. We prove both the existence and also provide formulas to construct them. Finally, we propose some conjectures and mention some future directions of works to conclude the thesis.

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes.

Submitted by Cláudia Bueno (claudiamoura18@gmail.com) on 2015-10-29T19:17:43Z No. of bitstreams: 2 Tese - Elisângela Silva Dias - 2015.pdf: 1107380 bytes, checksum: e288bc934158fa879639c403bb15ba54 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-11-03T14:30:02Z (GMT) No. of bitstreams: 2 Tese - Elisângela Silva Dias - 2015.pdf: 1107380 bytes, checksum: e288bc934158fa879639c403bb15ba54 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-11-03T14:30:02Z (GMT). No. of bitstreams: 2 Tese - Elisângela Silva Dias - 2015.pdf: 1107380 bytes, checksum: e288bc934158fa879639c403bb15ba54 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-09-09 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / Cluster algebras form a class of commutative algebra, introduced at the beginning of the millennium by Fomin and Zelevinsky. They are defined constructively from a set of generating variables (cluster variables) grouped into overlapping subsets (clusters) of fixed cardinality. Since its inception, the theory of cluster algebras found applications in many areas of science, specially in mathematics. In this thesis, we study, with computational focus, the recognition of cluster algebras of finite type. In 2006, Barot, Geiss and Zelevinsky showed that a cluster algebra is of finite type whether the associated graph is cyclically oriented, i.e., all chordless cycles of the graph are cyclically oriented, and whether the skew-symmetrizable matrix associated has a positive quasi-Cartan companion. At first, we studied the two topics independently. Related to the first part of the criteria, we developed an algorithm that lists all chordless cycles (polynomial on the length of those cycles) and another that checks whether a graph is cyclically oriented and, if so, list all their chordless cycles (polynomial on the number of vertices). Related to the second part of the criteria, we developed some theoretical results and we also developed a polynomial algorithm that checks whether a quasi-Cartan companion matrix is positive. The latter algorithm is used to prove that the problem of deciding whether a skew-symmetrizable matrix has a positive quasi-Cartan companion for general graphs is in NP class. We conjecture that this problem is in NP-complete class.We show that the same problem belongs to the class of polynomial problems for cyclically oriented graphs and, finally, we show that deciding whether a cluster algebra is of finite type also belongs to this class. / As álgebras cluster formam uma classe de álgebras comutativas introduzida no início do milênio por Fomin e Zelevinsky. Elas são definidas de forma construtiva a partir de um conjunto de variáveis geradoras (variáveis cluster) agrupadas em subconjuntos sobrepostos (clusters) de cardinalidade fixa. Desde a sua criação, a teoria das álgebras cluster encontrou aplicações em diversas áreas da matemática e afins. Nesta tese, estudamos, com foco computacional, o reconhecimento das álgebras cluster de tipo finito. Em 2006, Barot, Geiss e Zelevinsky mostraram que uma álgebra cluster é de tipo finito se o grafo associado é ciclicamente orientado, isto é, todos os ciclos sem corda do grafo são ciclicamente orientados, e se a matriz antissimetrizável associada possui uma companheira quase-Cartan positiva. Em um primeiro momento, estudamos os dois tópicos de forma independente. Em relação à primeira parte do critério, elaboramos um algoritmo que lista todos os ciclos sem corda (polinomial no tamanho destes ciclos) e outro que verifica se um grafo é ciclicamente orientado e, em caso positivo, lista todos os seus ciclos sem corda (polinomial na quantidade de vértices). Relacionado à segunda parte do critério, desenvolvemos alguns resultados teóricos e elaboramos um algoritmo polinomial que verifica se uma matriz companheira quase-Cartan é positiva. Este último algoritmo é utilizado para provar que o problema de decidir se uma matriz antissimetrizável tem uma companheira quase-Cartan positiva para grafos gerais está na classe NP. Conjecturamos que este problema pertence à classe NP-completa. Mostramos que o mesmo pertence à classe de problemas polinomiais para grafos ciclicamente orientados e, por fim, mostramos que decidir se uma álgebra cluster é de tipo finito também pertence a esta classe.