Partitionnement, recouvrement et colorabilité dans les graphes

Nos recherches traitent de coloration de graphes avec des contraintes de distance (coloration de packing) ou des contraintes sur le voisinage (coloration de Grundy). Soit S={si| i in N*} une série croissante d’entiers. Une S -coloration de packing est une coloration propre de sommets telle que tout ensemble coloré i est un si-packing (un ensemble où tous les sommets sont à distance mutuelle supérieure à si). Un graphe G est (s1,... ,sk)-colorable si il existe une S -coloration de packing de G avec les couleurs 1, ...,,k. Une coloration de Grundy est une coloration propre de sommets telle que pour tout sommet u coloré i, u est adjacent à un sommet coloré j, pour chaque j<i.Dans cette exposé, nous présentons des résultats connus à propos de la S-coloration de packing. Nous apportons de nouveaux résultats à propos de la S-coloration de packing, pour des classes de graphes telles que les chemins, les cycles et les arbres. Nous étudions en détail la complexité du problème de complexité associé à la S-coloration de packing, noté S -COL. Pour certaines instances de S -COL, nous caractérisons des dichotomies entre problèmes NP-complets et problèmes résolubles en tempspolynomial. Nous nous intéressons aux différentes grilles infinies, les grilles hexagonale, carrée, triangulaire et du roi et nous déterminons des propriétés de subdivisions d’un i-packing en plusieurs j-packings, avec j>i. Ces résultats nous permettent de déterminer des S-colorations de packings de ces grilles pour plusieurs séries d’entiers. Nous examinons une classe de graphe jamais étudiée en ce qui concerne la S -coloration de packing: les graphes subcubiques. Nous déterminons que tous les graphes subcubiques sont (1,2,2,2,2,2,2)-colorables et (1,1,2,2,3)-colorables. Un certain nombre de résultats sont prouvés pour certaines sous-classes des graphes subcubiques. Pour finir, nous nous intéressons au nombre de Grundy des graphes réguliers. Nous déterminons une caractérisation des graphes cubiques avec un nombre de Grundy de 4. De plus, nous prouvons que tous les graphes r-réguliers sans carré induit ont pour nombre de Grundy de r+1, pour r<5.