Ensembles indépendants dans les graphes : structure, décompositions et applications: L'un des problèmes les plus fondamentaux en théorie algorithmique des graphes est le calcul d'un ensemble indépendant maximum. Ce problème est étroitement lié à la modélisation des réseaux Wi-Fi, qui peuvent être naturellement représentés comme des graphes de conflits, où les sommets correspondent aux appareils et les arêtes représentent les interférences. En raison des contraintes des protocoles, les appareils actifs simultanément doivent former un ensemble indépendant. Par conséquent, les performances (débits) des appareils dépendent de la distribution des ensembles indépendants dans le graphe. Cette observation soulève des questions algorithmiques et structurelles naturelles : quelles classes de graphes garantissent de bonnes performances, comment attribuer efficacement les canaux, et comment estimer ces mesures de performance. Nous étudions d'abord les graphes dans lesquels chaque sommet appartient à au moins un ensemble indépendant maximum, appelés graphes 1-extendable. Ces graphes garantissent un niveau minimal de performance pour tous les dispositifs. Nous examinons la complexité de la reconnaissance de tels graphes et montrons que ce problème est Theta_2^p-complet, établissant ainsi sa complexité exacte. Motivés par le problème d'attribution de canaux, nous introduisons les k-partitions 1-extendable, où l'ensemble des sommets est partitionné en k sous-graphes, chacun vérifiant cette propriété. Bien que difficile en général, nous proposons des algorithmes en temps polynomial pour certaines classes de graphes restreintes, comme celles de graphes de largeur modulaire bornée. Nous considérons ensuite une notion plus robuste fondée sur la sous-coloration, où chaque partie induit une union disjointe de cliques, garantissant une stabilité vis-à-vis des suppressions de sommets. Nous étudions ce problème dans les graphes d'intersection géométriques, qui modélisent naturellement les réseaux sans fil. Pour des classes importantes telles que les graphes de disques unitaire, nous établissons des résultats de NP-complétude ainsi que des bornes sur le nombre de couleurs. Nous concevons également et évaluons expérimentalement une heuristique simple, montrant que la sous-coloration améliore significativement l'équité dans des scénarios pratiques d'attribution de canaux.Pour estimer les performances des dispositifs, nous analysons le modèle hard-core, une distribution de probabilité sur les ensembles indépendants, ainsi que la dynamique de Glauber associée. Nous montrons que, bien que le temps de mélange soit exponentiel en général, il devient sous-exponentiel pour plusieurs classes de graphes géométriques (par exemple 2^{O(sqrt{n})} pour les graphes de disques unitaire), ce qui conduit à des algorithmes randomisés pratiques. Nous obtenons en outre des bornes quasi-polynomiales sous certaines contraintes structurelles, telles qu'un nombre d'indépendance arborescent borné, et prouvons qu'elles sont optimales. Enfin, nous étudions l'existence d'algorithmes sous-exponentiels pour la sous-coloration dans les graphes géométriques. À l'aide d'une nouvelle décomposition fondée sur des graphes ayant de petits ensembles indépendants, nous concevons un algorithme s'exécutant en temps 2^{O(n^{1 - 1/(d+1)})} pour calculer des 2-sous-colorations et établissons des bornes inférieures correspondantes. Ce résultat ne s'inscrit pas dans les cadres classiques pour les graphes d'intersection géométriques. En nous appuyant sur cette approche, nous introduisons une autre décomposition, reposant également sur des graphes à petits ensembles indépendants comme briques de base, et obtenons un algorithme robuste sous-exponentiel pour le problème du chemin hamiltonien.