A 2-dipath k-colouring of an oriented graph G is an assignment of k colours, 1,2, . . . , k, to the vertices of G such that vertices joined by a directed path of length two are assigned different colours. The 2-dipath chromatic number is the minimum number of colours needed in such a colouring. There are two possible models, depending on whether adjacent vertices must also be assigned different colours. For both models of 2-dipath colouring we develop the basic theory, including characterizing the oriented graphs that can be 2-dipath coloured using a small number of colours, finding bounds on the 2-dipath chromatic number, determining the complexity of deciding the existence of a 2-dipath k-colouring, describing a homomorphism model, and showing how to determine the 2-dipath chromatic number of tournaments and bipartite tournaments. / Graduate

Dans ce travail, nous considérons le problème suivant : étant donné un graphe orienté D, contient-il une subdivision d’un digraphe fixé F ? Nous pensons qu’il existe une dichotomie entre les instances polynomiales et NP-complètes. Nous donnons plusieurs exemples pour les deux cas. En particulier, sauf pour cinq instances, nous sommes capable de classer tous les digraphes d’ordre 4. Alors que toutes les preuves NP-complétude sont faites par réduction de une version du problème 2-linkage en digraphes, nous utilisons différents outils algorithmiques pour prouver la solvabilité en temps polynomial de certains cas, certains d’entre eux impliquant des algorithmes relativement complexes. Les techniques varient des simples algorithmes de force brute, aux algorithmes basés sur des calculs maximale de flot, et aux décompositions en anses des digraphes fortement connexes, entre autres. Pour terminer, nous traitons le cas particulier où F étant une union disjointe de cycles dirigés. En particulier, nous montrons que les cycles dirigés de longueur au moins 3 possède la Propriété d’Erdos-Pósa : pour tout n, il existe un entier tn tel que pour tout digraphe D, soit D a n cycles dirigés disjoints de longueur au moins 3, soit il y a un ensemble T d’au plus tn sommets qui intersecte tous les cycles dirigés de longueur au moins 3. De ce résultat, nous déduisons que si F est l’union disjointe de cycles dirigés de longueur au plus 3, alors on peut décider en temps polynomial si un digraphe contient une subdivision de F. / In this work, we consider the following problem: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We believe that there is a dichotomy between NP-complete and polynomial-time solvable instances of this problem. We present many examples of both cases. In particular, except for five instances, we are able to classify all the digraphs F of order 4.While all NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, we use different algorithmic tools for proving polynomial-time solvability of certain instances, some of them involving relatively complicated algorithms. The techniques vary from easy brute force algorithms, algorithms based on maximum-flow calculations, handle decompositions of strongly connected digraphs, among others. Finally, we treat the very special case of F being the disjoint union of directed cycles. In particular, we show that the directed cycles of length at least 3 have the Erdos-Pósa Property: for every n, there exists an integer tn such that for every digraph D, either D contains n disjoint directed cycles of length at least 3, or there is a set T of tn vertices that meets every directed cycle of length at least 3. From this result, we deduce that if F is the disjoint union of directed cycles of length at most 3, then one can decide in polynomial time if a digraph contains a subdivision of F.

Un graphe mixte est un graphe simple tel que un sous-ensemble des arêtes a une orientation. Pour entiers non négatifs j et k, un graphe mixte-(j,k) est un graphe mixte avec j types des arcs and k types des arêtes. La famille de graphes mixte-(j,k) contient graphes simple, (graphes mixte−(0,1)), graphes orienté (graphes mixte−(1,0)) and graphe coloré arête −k (graphes mixte−(0,k)).Un homomorphisme est un application sommet entre graphes mixte−(j,k) que tel les types des arêtes sont conservés et les types des arcs et leurs directions sont conservés. Le nombre chromatique−(j,k) d’un graphe mixte−(j,k) est le moins entier m tel qu’il existe un homomorphisme à une cible avec m sommets. Quand on observe le cas de (j,k) = (0,1), on peut déterminer ces définitions correspondent à les définitions usuel pour les graphes.Dans ce mémoire on etude le nombre chromatique−(j,k) et des paramètres similaires pour diverses familles des graphes. Aussi on etude les coloration incidence pour graphes and digraphs. On utilise systèmes de représentants distincts et donne une nouvelle caractérisation du nombre chromatique incidence. On define le nombre chromatique incidence orienté et trouves un connexion entre le nombre chromatique incidence orienté et le nombre chromatic du graphe sous-jacent. / A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j,k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j,k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)−mixed graphs) and k−edge- coloured graphs ((0,k)−mixed graphs).A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. The (j,k)−chromatic number of a (j,k)−mixed graph is the least m such that an m−colouring exists. When (j,k)=(0,1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring.In this thesis we study the (j,k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1,0)−chromatic number, more commonly called the oriented chromatic number, and the (0,k)−chromatic number.In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs.

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.

nÃo hà / A anÃlise de imagens à um importante campo da visÃo computacional cujo propÃsito à extrair informaÃÃes significativas de imagens. Entre os vÃrios atributos relevantes que podem ser analisados, a textura à um dos mais importantes por ser uma fonte rica de informaÃÃes. O objetivo desta tese à desenvolver novos mÃtodos de anÃlise de textura (nÃveis de cinza e coloridas) baseados em modelos gravitacionais simplicados e caminhos mais curtos em grafos, que propiciem vetores de caracterÃsticas mais discriminativos do que os mÃtodos jà estabelecidos pela literatura. A primeira abordagem converte uma imagem em um sistema gravitacional simplificado cujo processo de colapso à explorado por meio de descritores de dimensÃo fractal e lacunaridade. A segunda abordagem converte os pixels de uma imagem em vÃrtices de um grafo ponderado nÃo-orientado e explora os caminhos mais curtos entre pares de vÃrtices em diferentes escalas e orientaÃÃes. Adicionalmente, nesta tese à proposto o estudo dessas abordagens na anÃlise de imagens de folhas de plantas para facilitar o moroso processo de taxonomia vegetal (problema este especialmente relevante para os botÃnicos) e de imagens mÃdicas para identificaÃÃo/classificaÃÃo de patologias, auxiliando o diagnÃstico mÃdico. Os experimentos sÃo realizados nas bases de imagens: Brodatz, UIUC, VisTex, USPTex, Outex, texturas foliares, parÃnquima paliÃÃdico, pap-smear e de tecido mamÃrio. Os resultados mais significativos de classificaÃÃo sÃo obtidos das bases UIUC, USPTex e parÃnquima paliÃÃdico, com taxas de acertos de 55,00%, 96,57% e 91,56% (menores taxas) obtidas pelos mÃtodos propostos, respectivamente. Essas taxas de acertos sÃo quase sempre superiores aos resultados obtidos pelos mÃtodos usados para comparaÃÃo, demonstrando que os mÃtodos propostos abrem promissoras fontes de pesquisa para os estudos de anÃlise de texturas em nÃveis de cinza e coloridas. / Image analysis is an important field of computer vision whose role is to extract significant information from images. Among several relevant attributes, texture is one of the most important because it is a rich source of information. This thesis aims to develop novel texture analysis methods (for grayscale and color images) based on simplified gravitational systems and shortest paths in graphs which provide feature vectors more discriminative than the methods already established in literature. The first approach converts an image into a simplified gravitational system whose collapse process is explored by using fractal dimension and lacunarity descriptors. The second approach converts the pixels of an image into vertices of a non-oriented weighted graph and explores the shortest paths between pairs of vertices in different scales and orientations. Additionally, this thesis proposes to apply these approaches to plant leaf identification (a relevant problem for botanists), and medical image identification/classication, increasing the confidence of medical diagnosis. The experiments are performed on the following image databases: Brodatz,UIUC, VisTex, USPTex, Outex, leaf textures, palisade parenchyma, pap-smear and breast tissues. The most significant comparison results are obtained from UIUC, USPTex and palisade parenchyma, with success rates of 55,00%, 96,57% and 91,56% (lower success rates) obtained by the proposed methods, respectively. These success rates are almost always superior to the results obtained by the methods used for comparison. This demonstrates that the proposed methods open promising sources of research in grayscale and color texture analysis.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2015-03-11T19:37:56Z No. of bitstreams: 2 Dissertação - Victor Hugo López Solís - 2012.pdf: 755677 bytes, checksum: ab64efbb1cbb6b6d5b9683cad6f75d6e (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2015-03-13T18:58:33Z (GMT) No. of bitstreams: 2 Dissertação - Victor Hugo López Solís - 2012.pdf: 755677 bytes, checksum: ab64efbb1cbb6b6d5b9683cad6f75d6e (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-03-13T18:58:59Z (GMT). No. of bitstreams: 2 Dissertação - Victor Hugo López Solís - 2012.pdf: 755677 bytes, checksum: ab64efbb1cbb6b6d5b9683cad6f75d6e (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2012-03-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Our work has as main objective, to establish conditions for a canonical form for elements of a ring, semigroup or algebraic structure similar. This result is obtained through the main Theorem 3.10 (The Lemma of Bergman’s Diamond) with applications. / O nosso trabalho tem como objetivo principal, estabelecer condições para obter uma forma canônica para os elementos de um anel, semigrupo ou estrutura algébrica similar. Isto é obtido através do resultado principal, o Teorema 3.10 (O Lema do Diamante de Bergman), com aplicações.

La littérature en science politique sur les changements climatiques identifie les clivages au sein de l’opinion publique comme contribuant à l’inaction des politiques sur la question climatique. Comprendre l’ampleur de cette polarisation et les axes sur lesquels elle se décline est une première étape essentielle pour adresser cette polarisation. Ce mémoire cherche à décrire comment se décline l’évolution de la polarisation de l’opinion publique au Canada autour des changements climatiques et comment elle a évolué pendant la dernière décennie. La revue de littérature identifie trois principaux axes de polarisation autour de la question climatique au Canada : le soutien pour un parti politique, l’idéologie politique et la région. Les données utilisées sont tirées d’une série de sondages menés tous les ans entre 2011 et 2021 à travers le Canada par le professeur Erick Lachapelle. Trois mesures de l’opinion sur la question climatique sont utilisées pour observer la polarisation : la croyance aux changements climatiques et en ses causes anthropogéniques, la perception d’une menace et le soutien pour une taxe carbone. L’analyse des résultats combine des analyses descriptives et des régressions linéaires multivariées. Ces analyses montrent une polarisation principalement partisane et idéologique, mais également régionale, qui oppose les provinces pétrolières au reste du Canada. L’opinion publique s’est de plus en plus polarisée pendant la dernière décennie, mais principalement autour du débat sur la taxe carbone. De plus, la polarisation partisane était particulièrement marquée lorsque les changements climatiques étaient saillants dans les débats politiques lors des élections fédérales de 2015 et 2019. / The political science literature on climate change identifies public opinion polarisation as significantly contributing to policy inaction on the climate issue. Understanding the extent of this polarization and the axes along which it occurs is an essential first step in addressing it. This paper seeks to describe how the polarization of public opinion in Canada around climate change has evolved over the past decade. The literature review identifies three main axes of polarization on the climate issue in Canada: support for a political party, political ideology and region. The data used is drawn from a series of surveys conducted annually between 2011 and 2021 across Canada by Professor Erick Lachapelle. Three measures of opinion on the climate issue are used to observe polarization: belief in climate change and its anthropogenic causes, threat perception and support for a carbon tax. The analysis of the results combines descriptive analyses and multivariate linear regressions. These analyses show a mainly partisan and ideological polarization, but also a regional polarization, which pits the oil-producing provinces against the rest of Canada. Public opinion has become increasingly polarized over the past decade, but mainly around the carbon tax debate. Moreover, partisan polarization was particularly pronounced when climate change is salient in the political debate during the 2015 and 2019 federal elections.