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 Réseaux de Capteurs Sans Fil (RCSFs) constituent une classe particulière des réseaux Ad hoc, faisant l'objet de recherches intensives. Ils sont considérés comme un outil très puissant pour connecter le monde physique et le monde numérique. Ils se composent d'un grand nombre de noeuds capteurs dotés de ressources limitées en termes d'énergie, de portée de capture et de communication, de vitesse de traitement et de capacité de stockage. Ils sont déployés dans un environnement intérieur ou extérieur, et ce dans de nombreux domaines d'application tels que l'armée, l'environnement, la santé, la maison et l'agriculture. La rareté des ressources des noeuds capteurs et la non fiabilité des liaisons sans fil motivent la plupart des problématiques dans le domaine des RCSFs, à savoir l'énergie, la couverture, la connectivité, le routage, la tolérance aux pannes et la sécurité. L'objectif de cette thèse est de proposer un protocole de surveillance inter-couches, à efficacité énergétique et fiable, pour la surveillance des zones sensibles clôturées, tel qu'un site pétrolier ou nucléaire, utilisant les réseaux de capteurs sans fil avec un cycle d'activité, et avec prise en compte des liens asymétriques dus au phénomène de l'irrégularité de la radio. Initialement, le protocole proposé identifie les noeuds de bordure du RCSF pour les utiliser comme nœuds sentinelles, c.-à-d., des noeuds qui sont toujours dans un état actif. Les noeuds restants sont utilisés en tant que noeuds relais avec un cycle d'activité, pendant la phase de routage des alertes vers le noeud puits. Le processus d'identification des noeuds de bordure ainsi que le routage des alertes, sont assurés par le protocole Greedy Perimeter Stateless Routing through Symmetrical Links (GPSR-SL) qui est une version améliorée du protocole GPSR, reposant sur un graphe de connectivité représenté sous forme de disques non-unité (N-UDG). Le protocole de surveillance inter-couches proposé a été implémenté et ses performances ont été évaluées en utilisant l'environnement de simulation OMNeT++/Castalia. Les résultats de performance montrent que ce protocole permet d'obtenir un ratio de livraison de paquets plus élevé d'environ 3.63%, une efficacité énergétique et une latence satisfaisante par rapport au même protocole basé sur le GPSR original. / Wireless Sensor Networks (WSNs) are a special class of Ad hoc networks, which are under intensive research.They are considered as a very powerful tool to connect the physical and the digital worlds. They consist of a largenumber of sensor nodes that are characterized with limited resources in terms of energy, range of sensing and communication, processing speed and storage capacity.They are deployed in an indoor or outdoor environment in many application domains such as army, environment, health, home and agriculture. The scarcity of sensor node resources and the unreliability of wireless links drive most of the research issues in the field of WSNs, namely energy, coverage, connectivity, routing, fault tolerance and security. The aim of this thesis is to propose an energyefficient and reliable cross-layer surveillance protocol for sensitive fenced areas, such as oil or nuclear sites, using duty-cycled WSNs with asymmetrical links due to the radio irregularity phenomenon. Initially, the proposed protocol identifies the boundary nodes of the deployedWSN, to be used as sentinel nodes, i.e., nodes that are always in an active state. The remaining nodes are usedas duty-cycled relay nodes during the routing phase to relay alerts towards the sink. The boundary nodes identification process and alert routing are both performed using an enhanced version of the Greedy Perimeter Stateless Routing (GPSR) protocol, referred to as GPSR over Symmetrical Links (GPSR-SL) and which relies on a Non Unit Disk Graph (N-UDG). The proposed cross-layer surveillance protocol has been implemented and its performance has been evaluated under the OMNeT++/Castalia simulation environment. Performance results show that this protocol achieves higher Packet Delivery Ratio by up to 3.63%, energy .efficiency and satisfactory latency when compared to the same protocol based on the original GPSR.