We define a variation of injective oriented colouring as reflexive injective oriented colouring, or rio-colouring for short, which requires an oriented colouring to be injective on the neighbourhoods of the underlying graph, without requiring the colouring to be proper. An analysis of the complexity of the problem of deciding whether an oriented graph has a k-rio-colouring is considered, and we find a dichotomy for the values of k below 3 and above, being in P or NP-complete, respectively. Characterizations are given for the oriented graphs resulting from the polynomial-time solvable cases, and bounds are given for the rio-chromatic number in terms of maximum in-degree and out-degree, in general, and for oriented trees. Also, a polynomial-time algorithm is developed to aid in the rio-colouring of oriented trees.

Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-11-09T13:29:03Z No. of bitstreams: 1 arquivototal.pdf: 3106591 bytes, checksum: 681468331a75115cdd412b8abaa0633f (MD5) / Approved for entry into archive by Maria Suzana Diniz (msuzanad@hotmail.com) on 2015-11-09T13:50:10Z (GMT) No. of bitstreams: 1 arquivototal.pdf: 3106591 bytes, checksum: 681468331a75115cdd412b8abaa0633f (MD5) / Made available in DSpace on 2015-11-09T13:50:10Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 3106591 bytes, checksum: 681468331a75115cdd412b8abaa0633f (MD5) Previous issue date: 2015-04-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work we study the graph theory, which although it is somewhat widespread content, including academia is extremely important for solving many mathematical problems and physical models. Moreover, this theme can be found in applications in several areas, including quote: computer, electrical, genetic. We adopt the bibliographic research and exploratory research to deal with the issue at hand, trying to de ne and clarify the aforesaid theory, but also contribute to its spread, which enables members of the basic and higher education have a contact with such an important and fruitful know, since elementary considerations graphs brings us closer to scienti c research. We alternate concepts and statements of lemmas and theorems to solve problems. We use simple language, so that a high school student can understand, without, however, distancing us from mathematical rigor. In time, we present the four color theorem the number of Ramsey, with detailed statements of the latter result. Finally, we use concepts and purely combinatorial results and probability, using the probabilistic method to prove the existence of graphs with certain properties that are di cult construction and, through this evidence, get other desired graph. / Neste trabalho, estudamos a teoria dos grafos, que embora seja um conteúdo pouco difundido, inclusive em âmbito acadêmico é de extrema importância para a resolução de inúmeros problemas matemáticos e modelos físicos. Além disso, essa temática pode ser veri cada em aplicações nas mais diversas áreas, entre as quais citamos: computacional, elétrica, genética. Adotamos a investigação bibliográ ca e a pesquisa exploratória para tratar o tema em questão, procurando de nir e esclarecer a teoria sobredita, como também contribuir em sua difusão, o que possibilita aos integrantes da educação básica e superior terem um contato com tão importante e fecundo saber, uma vez que considerações elementares sobre grafos nos aproxima da pesquisa cientí ca. Intercalamos os conceitos e as demonstrações de lemas e teoremas com a apresentação e resolução de problemas. Empregamos uma linguagem simples, de forma que um aluno do ensino médio possa compreender, sem, no entanto, nos distanciar do rigor matemático. Em tempo, apresentamos o teorema das quatro cores e o número de Ramsey, com demonstrações detalhadas deste último resultado. Por m, utilizamos conceitos e resultados puramente de combinatória e probabilidade, utilizando o método probabilístico para provar a existência de grafos com determinadas propriedades que são de difícil construção e, por meio desta comprovação, chegar a outro grafo desejado.

La thèse porte sur les deux thèmes des Jeux combinatoires et de la théorie des graphes. Elle est divisée en deux parties.1) Le jeu de Domination et ses variantes: Il s'agit d'un jeu combinatoire qui consiste à marquer les sommets d'un graphe de telle sorte qu'un sommet marqué n'ait aucun voisin marqué. Le joueur marquant le dernier sommet est déclaré gagnant. Le calcul des stratégies gagnantes étant NP-difficile pour un graphe quelconque, nous avons étudié des familles particulières de graphes comme les chemins, les scies ou les chenilles. Pour ces familles on peut savoir en temps polynomial si un graphe est perdant. Nous avons également étudié 28 variantes du jeu de domination, dont les 12 variantes définies par J. Conway sur un jeu combinatoire quelconque. 2) Le nombre chromatique ludique des arbres: Ce paramètre est calculé à partir d'un jeu de coloration où Alice et Bob colorient alternativement et proprement un sommet d'un graphe G avec l'une des k couleurs. L'objectif d'Alice est de colorier complètement le graphe alors que Bob doit l'en empêcher. Nous nous sommes intéressés au jeu avec 3 couleurs sur un arbre T. Nous souhaitons déterminer les arbres ayant un nombre chromatique ludique 3, soit ceux pour lesquels Alice a une stratégie gagnante avec 3 couleurs. Ce problème semblant difficile à résoudre sur les arbres, nous avons résolu des sous-familles: les 1-chenilles puis les chenilles sans trous. / Part 1: Domination Game and its variantsDomination game is a combinatorial game that consists in marking vertices of a graph so that a marked vertex has no marked neighbors. The first player unable to mark a vertex loses the game.Since the computing of winning strategies is an NP-hard problem for any graphs, we examine some specific families of graphs such as complete k-partite graphs, paths or saws. For these families, we establish the set of losing elements. For other families, such as caterpillars, we prove that exists a polynomial algorithm for the computation of outcome and winning strategies. No polynomial algorithm has been found to date for more general families, such as trees.We also study 28 variants of Domination game, including the 12 variants defined by J. Conway for any combinatorial game. Using game functions, we find the set of losing paths for 10 of these 12 variants. We also investigate 16 variants called diameter, for instance when rules require to play on the component that has the largest diameter.Part 2: The game chromatic number of treesThis parameter is computed from a coloring game: Alice and Bob alternatively color the vertices of a graph G, using one of the k colors in the color set. Alice has to achieve the coloring of the entire graph whereas Bob has to prevent this. Faigle and al. proved that the game chromatic number of a tree is at most 4. We undertake characterization of trees with a game chromatic number of 3. Since this problem seems difficult for general trees, we focus on sub-families: 1-caterpillars and caterpillars without holes.For these families we provide the characterization and also compute winning strategies for Alice and Bob. In order to do so, we are led to define a new notion, the bitype, that for a partially-colored graph G associates two letters indicating who has a winning strategy respectively on G and G with an isolated vertex. Bitypes allow us to demonstrate several properties, in particular to compute the game chromatic number of a graph from the bitypes of its connected components.

This PhD thesis is comprised of 3 results in computational geometry and graph theory. In the first paper, I demonstrate that the piercing number of a set S of pairwise intersecting convex shapes in the plane is bounded by O(\alpha(S)), where \alpha(S) is the fatness of the set S, improving upon the previous upper-bound of O(\alpha(S)^2). In the second article, I show that anagram-free vertex colouring of a 2\times n square grid requires a number of colours that increases with n. This answers an open question in Wilson's thesis and shows that even graphs of pathwidth 2 do not have anagram-free colouring with a bounded number of colours. The third article is a study on the geodesic anagram-free chromatic number of chordal and interval graphs. \emph{Geodesic anagram-free chromatic number} is defined as the minimum number of colours required to colour a graph such that all shortest paths between any pair of vertices are coloured anagram-free. In particular, I prove that the geodesic anagram-free chromatic number of a chordal graph G is 32p'w, where p' is the pathwidth of the subtree intersection representation graph (tree) of G, and w is the clique number of G. Additionally, I prove that the geodesic anagram-free chromatic number of an interval graph is bounded by 32p, where p is the pathwidth of the interval graph. This PhD thesis is comprised of 3 results in computational geometry and graph theory.

Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissance / Two problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions it is true. We prove that b(G) = d+1 if G is a d-regular graph containing neither a cycle of order 4 nor of order 6. Then, we provide specific conditions on the vertices of a d-regular graph G with no cycle of order 4 so that b(G) = d + 1. Cabello and Jakovac proved that if v(G) ≥ 2d3 - d2 + d, then b(G) = d + 1, where G is a d-regular graph. We improve this bound by proving that if v(G) ≥ 2d3 - 2d2 + 2d, then b(G) = d+1 for a d-regular graph G. 2. Graph Packing Problem : Graph packing problem is a classical problem in graph theory and has been extensively studied since the early 70's. Consider a permutation σ : V (G) → V (Kn), the function σ* : E(G) → E(Kn) such that σ *(xy) = σ *(x) σ *(y) is the function induced by σ. We say that there is a packing of k copies of G into the complete graph Kn if there exist k permutations σ i : V (G) → V (Kn), where i = 1,…, k, such that σ*i (E(G)) ∩ σ*j (E(G)) = ɸ for I ≠ j. A packing of k copies of a graph G will be called a k-placement of G. The kth power Gk of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. Kheddouci et al. proved that for any non-star tree T there exists a 2-placement σ on V (T). We introduce a new variant of graph packing problem, called the labeled packing of a graph into its power graph

著色問題(graph coloring problem)的研究已行之有年，並衍生出廣泛的實際應用，但還缺乏一般化的著色問題模型。本論文建構一般化的著色問題模型，其目標函數包含顏色成本的固定支出和點著色變動成本。此著色模型為0/1整數線性規畫模型，其限制式含有選點問題(node packing problem)的限制式。我們利用圖中的極大團(maximal clique)所構成的強力限制式，取代原有的選點限制式，縮短求解時間。我們更進一步舉出一個特殊指派問題並將此著色模型應用於此指派問題上。本論文亦針對此指派問題發展了一個演算法來尋找極大團。計算結果顯示極大團限制式對於此著色問題模型的求解有極大的效益。 / The graph coloring problem (GCP) has been studied for a long time and it has a wide variety of applications. A straightforward formulation of graph coloring problem has not been formulated yet. In this paper, we formulate a general GCP model that concerns setup cost and variable cost of different colors. The resulting model is an integer program that involves the packing constraint. The packing constraint in the GCP model can be replaced by the maximal clique constraint in order to shorten the solution time. A special assignment problem is presented which essentially is a GCP model application. An algorithm of finding maximal cliques for this assignment problem is developed. The computational results show the efficiency of maximal clique constraints for the GCP problem.

Le calcul du nombre chromatique et la détermination d'une colo- ration optimale des sommets d'un graphe sont des problèmes NP- difficiles en général. Ils peuvent cependant être résolus en temps po- lynomial dans les graphes parfaits. Par ailleurs, la perfection d'un graphe peut être décidée efficacement. Les graphes parfaits sont caractérisés par la structure de leur poly- tope des stables : les facettes non-triviales sont définies exclusivement par des inégalités de cliques. Réciproquement, une structure similaire des facettes du polytope des stables détermine-t-elle des propriétés combinatoires et algorithmiques intéressantes? Un graphe est h-parfait si les facettes non-triviales de son polytope des stables sont définies par des inégalités de cliques et de circuits impairs. On ne connaît que peu de résultats analogues au cas des graphes parfaits pour la h-perfection, et on ne sait pas si les problèmes sont NP-difficiles. Par exemple, les complexités algorithmiques de la re- connaissance des graphes h-parfaits et du calcul de leur nombre chro- matique sont toujours ouvertes. Par ailleurs, on ne dispose pas de borne sur la différence entre le nombre chromatique et la taille maxi- mum d'une clique d'un graphe h-parfait. Dans cette thèse, nous montrons tout d'abord que les opérations de t-mineurs conservent la h-perfection (ce qui fournit une extension non triviale d'un résultat de Gerards et Shepherd pour la t-perfection). De plus, nous prouvons qu'elles préservent la propriété de décompo- sition entière du polytope des stables. Nous utilisons ce résultat pour répondre négativement à une question de Shepherd sur les graphes h-parfaits 3-colorables. L'étude des graphes minimalement h-imparfaits (relativement aux t-mineurs) est liée à la recherche d'une caractérisation co-NP com- binatoire de la h-perfection. Nous faisons l'inventaire des exemples connus de tels graphes, donnons une description de leur polytope des stables et énonçons plusieurs conjectures à leur propos. D'autre part, nous montrons que le nombre chromatique (pondéré) de certains graphes h-parfaits peut être obtenu efficacement en ar- rondissant sa relaxation fractionnaire à l'entier supérieur. Ce résultat implique notamment un nouveau cas d'une conjecture de Goldberg et Seymour sur la coloration d'arêtes. Enfin, nous présentons un nouveau paramètre de graphe associé aux facettes du polytope des couplages et l'utilisons pour donner un algorithme simple et efficace de reconnaissance des graphes h- parfaits dans la classe des graphes adjoints. / Computing the chromatic number and finding an optimal coloring of a perfect graph can be done efficiently, whereas it is an NP-hard problem in general. Furthermore, testing perfection can be carried- out in polynomial-time. Perfect graphs are characterized by a minimal structure of their sta- ble set polytope: the non-trivial facets are defined by clique-inequalities only. Conversely, does a similar facet-structure for the stable set polytope imply nice combinatorial and algorithmic properties of the graph ? A graph is h-perfect if its stable set polytope is completely de- scribed by non-negativity, clique and odd-circuit inequalities. Statements analogous to the results on perfection are far from being understood for h-perfection, and negative results are missing. For ex- ample, testing h-perfection and determining the chromatic number of an h-perfect graph are unsolved. Besides, no upper bound is known on the gap between the chromatic and clique numbers of an h-perfect graph. Our first main result states that the operations of t-minors keep h- perfection (this is a non-trivial extension of a result of Gerards and Shepherd on t-perfect graphs). We show that it also keeps the Integer Decomposition Property of the stable set polytope, and use this to answer a question of Shepherd on 3-colorable h-perfect graphs in the negative. The study of minimally h-imperfect graphs with respect to t-minors may yield a combinatorial co-NP characterization of h-perfection. We review the currently known examples of such graphs, study their stable set polytope and state several conjectures on their structure. On the other hand, we show that the (weighted) chromatic number of certain h-perfect graphs can be obtained efficiently by rounding-up its fractional relaxation. This is related to conjectures of Goldberg and Seymour on edge-colorings. Finally, we introduce a new parameter on the complexity of the matching polytope and use it to give an efficient and elementary al- gorithm for testing h-perfection in line-graphs.

Un graphe métrique G(X;D) est un graphe dont l’ensemble des sommets est l’ensemble X des points d’un espace métrique (X; d), et dont les arêtes relient les paires fx; yg de sommets telles que d(x; y) 2 D. Dans cette thèse, nous considérons deux problèmes qui peuvent être interprétés comme des problèmes de graphes métriques dans Rn. Premièrement, nous nous intéressons au célèbre problème d’empilements de sphères, relié au graphe métrique G(Rn; ]0; 2r[) pour un rayon de sphère r donné. Récemment, Venkatesh a amélioré d’un facteur log log n la meilleure borne inférieure connue pour un empilement de sphères donné par un réseau, pour une suite infinie de dimensions n. Ici nous prouvons une version effective de ce résultat, dans le sens où l’on exhibe, pour la même suite de dimensions, des familles finies de réseaux qui contiennent un réseaux dont la densité atteint la borne de Venkatesh. Notre construction met en jeu des codes construits sur des corps cyclotomiques, relevés en réseaux grâce à un analogue de la Construction A. Nous prouvons aussi un résultat similaire pour des familles de réseaux symplectiques. Deuxièmement, nous considérons le graphe distance-unité G associé à une norme k_k. Le nombre m1 (Rn; k _ k) est défini comme le supremum des densités réalisées par les stables de G. Si la boule unité associée à k _ k pave Rn par translation, alors il est aisé de voir que m1 (Rn; k _ k) > 1 2n . C. Bachoc et S. Robins ont conjecturé qu’il y a égalité. On montre que cette conjecture est vraie pour n = 2 ainsi que pour des régions de Voronoï de plusieurs types de réseaux en dimension supérieure, ceci en se ramenant à la résolution de problèmes d’empilement dans des graphes discrets. / A distance graph G(X;D) is a graph whose set of vertices is the set of points X of a metric space (X; d), and whose edges connect the pairs fx; yg such that d(x; y) 2 D. In this thesis, we consider two problems that may be interpreted in terms of distance graphs in Rn. First, we study the famous sphere packing problem, in relation with thedistance graph G(Rn; (0; 2r)) for a given sphere radius r. Recently, Venkatesh improved the best known lower bound for lattice sphere packings by a factor log log n for infinitely many dimensions n. We prove an effective version of this result, in the sense that we exhibit, for the same set of dimensions, finite families of lattices containing a lattice reaching this bound. Our construction uses codes over cyclotomic fields, lifted to lattices via Construction A. We also prove a similar result for families of symplectic lattices. Second, we consider the unit distance graph G associated with a norm k _ k. The number m1 (Rn; k _ k) is defined as the supremum of the densities achieved by independent sets in G. If the unit ball corresponding with k _ k tiles Rn by translation, then it is easy to see that m1 (Rn; k _ k) > 1 2n . C. Bachoc and S. Robins conjectured that the equality always holds. We show that this conjecture is true for n = 2 and for several Voronoï cells of lattices in higher dimensions, by solving packing problems in discrete graphs.