Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Dans cette thèse, nous nous intéressons à differentes colorations des sommets d’un graphe et aux homomorphismes de graphes. Nous nous intéressons plus spécialement aux graphes planaires et aux graphes peu denses. Nous considérons la coloration propre des sommets, la coloration acyclique, la coloration étoilée, lak-forêt-coloration, la coloration fractionnaire et la version par liste de la plupart de ces concepts.Dans le Chapitre 2, nous cherchons des conditions suffisantes de 3-liste colorabilité des graphes planaires. Ces conditions sont exprimées en termes de sous-graphes interdits et nos résultats impliquent plusieurs résultats connus.La notion de la coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud, et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. Dans le Chapitre 3, on obtient des conditions suffisantes pour qu’un graphe planaire admette une k-coloration acyclique par liste avec k 2 f3; 4; 5g.Dans le Chapitre 4, nous montrons que tout graphe subcubique est 6-étoilé coloriable.D’autre part, Fertin, Raspaud et Reed ont montré que le graphe de Wagner ne peut pas être 5-étoilé-coloriable. Ce fait implique que notre résultat est optimal. De plus, nous obtenons des nouvelles bornes supérieures sur la choisissabilité étoilé d’un graphe planaire subcubique de maille donnée.Une k-forêt-coloration d’un graphe G est une application ¼ de l’ensemble des sommets V (G) de G dans l’ensemble de couleurs 1; 2; ¢ ¢ ¢ ; k telle que chaque classede couleur induit une forêt. Le sommet-arboricité de G est le plus petit entier ktel que G a k-forêt-coloration. Dans le Chapitre 5, nous prouvons une conjecture de Raspaud et Wang affirmant que tout graphe planaire sans triangles intersectants admet une sommet-arboricité au plus 2.Enfin, au Chapitre 6, nous nous concentrons sur le problème d’homomorphisme des graphes peu denses dans le graphe de Petersen. Plus précisément, nous prouvons que tout graphe sans triangles ayant un degré moyen maximum moins de 5=2 admet un homomorphisme dans le graphe de Petersen. En outre, nous montrons que la borne sur le degré moyen maximum est la meilleure possible. / In this thesis, we are interested in various vertex coloring and homomorphism problems of graphs with special emphasis on planar graphs and sparsegraphs. We consider proper vertex coloring, acyclic coloring, star coloring, forestcoloring, fractional coloring and the list version of most of these concepts.In Chapter 2, we consider the problem of finding sufficient conditions for a planargraph to be 3-choosable. These conditions are expressed in terms of forbiddensubgraphs and our results extend several known results.The notion of acyclic list coloring of planar graphs was introduced by Borodin,Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that everyplanar graph is acyclically 5-choosable. In Chapter 3, we obtain some sufficientconditions for planar graphs to be acyclically k-choosable with k 2 f3; 4; 5g.In Chapter 4, we prove that every subcubic graph is 6-star-colorable. On theother hand, Fertin, Raspaud and Reed showed that the Wagner graph cannot be5-star-colorable. This fact implies that our result is best possible. Moreover, weobtain new upper bounds on star choosability of planar subcubic graphs with givengirth.A k-forest-coloring of a graph G is a mapping ¼ from V (G) to the set f1; ¢ ¢ ¢ ; kgsuch that each color class induces a forest. The vertex-arboricity of G is the smallestinteger k such that G has a k-forest-coloring. In Chapter 5, we prove a conjecture ofRaspaud and Wang asserting that every planar graph without intersecting triangleshas vertex-arboricity at most 2.Finally, in Chapter 6, we focus on the homomorphism problems of sparse graphsto the Petersen graph. More precisely, we prove that every triangle-free graph withmaximum average degree less than 5=2 admits a homomorphism to the Petersengraph. Moreover, we show that the bound on the maximum average degree in ourresult is best possible.

Dans cette thèse, nous nous intéressons à différentes notions de colorations sous contraintes. Nous nous intéressons plus spécialement à la coloration acyclique, à la coloration forte d'arêtes et à la coloration d'arêtes sommets adjacents distinguants.Dans le Chapitre 2, nous avons étudié la coloration acyclique. Tout d'abord nous avons cherché à borner le nombre chromatique acyclique pour la classe des graphes de degré maximum borné. Ensuite nous nous sommes attardés sur la coloration acyclique par listes. La notion de coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. De notre côté, nous avons proposé des conditions suffisantes de 3-liste coloration acyclique des graphes planaires. Dans le Chapitre 3, nous avons étudié la coloration forte d'arêtes des graphes subcubiques en majorant l'indice chromatique fort en fonction du degré moyen maximum. Nous nous sommes également intéressés à la coloration forte d'arêtes des graphes subcubiques sans cycles de longueurs données et nous avons également obtenu une majoration optimale de l'indice chromatique fort pour la famille des graphes planaires extérieurs. Nous avons aussi présenté différents résultats de complexité pour la classe des graphes planaires subcubiques. Enfin, au Chapitre 4, nous avons abordé la coloration d'arêtes sommets adjacents distinguants en déterminant les majorations de l'indice avd-chromatique en fonction du degré moyen maximum. Notre travail s'inscrit dans la continuité de celui effectué par Wang et Wang en 2010. Plus précisément, nous nous sommes focalisés sur la famille des graphes de degré maximum au moins 5. / In this thesis, we are interested in various coloring of graphs under constraints. We study acyclic coloring, strong edge coloring and adjacent vertex-distinguishing edge coloring.In Chapter 2, we consider acyclic coloring and we bound the acyclic chromatic number by a function of the maximum degree of the graph. We also study acyclic list coloring. The notion of acyclic list coloring of planar graphs was introduced by Borodin, Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that every planar graph is acyclically 5-choosable. We obtain some sufficient conditions for planar graphs to be acyclically 3-choosable.In Chapter 3, we study strong edge coloring of graphs. We prove some upper bounds of the strong chromatic index of subcubic graphs as a function of the maximum average degree. We also obtain a tight upper bound for the minimum number of colors in a strong edge coloring of outerplanar graphs as a function of the maximum degree. We also prove that the strong edge k-colouring problem, when k=4,5,6, is NP-complete for subcubic planar bipartite graphs with some girth condition. Finally, in Chapter 4, we focus on adjacent vertex-distinguishing edge coloring, or avd-coloring, of graphs. We bound the avd-chromatic number of graphs by a function of the maximum average degree. This work completes a result of Wang and Wang in 2010.

Les analogues de nucléosides ont reçu une attention particulière en raison de leurs importantes applications anticancéreuses et antivirales. Dans cette thèse, de nouveaux analogues nucléosidiques de type 1′,2′-cis et 1′,2′-trans ribo portant un centre stéréogénique quaternaire fonctionnalisé en position C3′ ont été synthétisés par des réactions de N-glycosylation stéréosélectives, qui ont été contrôlées en installant différents types de groupes protecteurs sur le C2′ substituant hydroxyle. Le précurseur acyclique critique de 2,4-syn diol a été obtenu par réduction diastéréosélective d’une β-hydroxycétone en utilisant la délivrance d'hydrure intermoléculaire. Une approche pour une séparation facile des 2,4-syn et 2,4-anti diols par protection/déprotection acétonide a été établie, de sorte que le 2,4-syn diol pur puisse être rapidement accessible par oxydation allylique successive et protection acétonide. Une stratégie alternative a également été développée pour la préparation d'analogues nucléosidiques en C1′-β de type ribo portant un centre quaternaire C3′ avec un groupe hydroxyle C5′ libre. Dans cette stratégie, les diacétates de type ribo ont servi de donneur de glycosyle qui ont été synthétisés à partir d’une époxydation diastéréosélective d’un précurseur de glycal. La réaction énantiosélective consécutive de Mukaiyama aldol et le transfert d'allyle intramoléculaire de radicaux libres catalysé par photoredox ont été établis et développés dans notre laboratoire pour installer le centre stéréogénique quaternaire. Des nucléosides 5′-triphosphates portant soit une purine soit une pyrimidine ont ensuite été synthétisés et sont testés contre le cancer et les infections virales. De plus, l'analogue L-1′,2′-cis-4′-thionucléoside portant un centre quaternaire stéréogénique fonctionnalisé en position C3′ avec un substituant hydroxyle en C2′ a été synthétisé par une stratégie acyclique avec 1′,2′-syn thioaminal précurseur, qui a subi une cyclisation intramoléculaire de type SN2 de type S1′→C4′. Le 1′,2′-syn thioaminal a été synthétisé par une addition de nucléobase diastéréosélective sur un dithioacétal. / Nucleoside analogues have received extensive attention due to their important anticancer and antiviral applications. In this thesis, novel 1′,2′-cis and trans ribo-like nucleoside analogues bearing an all-carbon C3′ quaternary stereogenic center were synthesized using stereoselective N-glycosylation reactions, which were controlled by installing different types of protecting groups on the C2′ hydroxyl substituent. The critical acyclic 2,4-syn diol precursor was obtained by diastereoselective reduction of a β-hydroxy ketone using intermolecular hydride delivery. An approach for easy separation of the 2,4-syn and 2,4-anti diols through acetonide protection/deprotection was established to rapidly access the pure 2,4-syn diol through successive allylic oxidation and acetonide protection. An alternative strategy was also developed for the preparation of ribo-like C1′-β nucleoside analogues bearing an all-carbon C3′ quaternary center with a free C5′ hydroxyl group. In this strategy, ribo-like diacetates served as the glycosyl donors which were synthesized from a diastereoselective epoxidation of a glycal precursor. A consecutive enantioselective Mukaiyama aldol reaction followed by a photoredox catalyzed free radical intramolecular allyl transfer were established and developed in our lab to install the all-carbon quaternary stereogenic center. Nucleoside 5′-triphosphates bearing either a purine or a pyrimidine nucleobase were then synthesized and are currently being tested against cancer and viral infections. In addition, L-1′,2′-cis-4′-thionucleoside analogues bearing an all-carbon C3′ stereogenic quaternary center along with a C2′ hydroxyl substituent were synthesized using an acyclic strategy from a 1′,2′-syn thioaminal precursor followed by a S1′→C4′ intramolecular SN2-like cyclization. The 1′,2′-syn thioaminal was synthesized by a diastereoselective nucleobase addition onto a dithioacetal.