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.
| Identifer | oai:union.ndltd.org:theses.fr/2011BOR14390 |
| Date | 05 December 2011 |
| Creators | Hocquard, Hervé |
| Contributors | Bordeaux 1, Raspaud, André, Montassier, Mickaël |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0205 seconds