Sur divers problèmes de coloration de graphes

Abstract

Dans cette thèse, nous étudions des problèmes de coloration de graphe. Nous nous intéressons à deux familles de colorations.La première consiste à colorer des graphes, appelés graphes signés, modélisant des relations sociales. Ceux-ci disposent de deux types d’arêtes : les arêtes positives pour représenter l’amitié et les arêtes négatives pour l’animosité. Nous pouvons colorer des graphes signés à travers la notion d’homomorphisme : le nombre chromatique d’un graphe signé (G, σ) est alors le nombre minimum de sommets d’un graphe signé (H, π) tel que (G, σ) admet un homomorphisme vers (H, π). Nous étudions la complexité des homomorphismes de graphes signés quand la cible est fixée et quand l’entrée peut être modifiée, et obtenons des dichotomies P/NP-complet et FPT/W[1]-difficile. Nous obtenons des bornes supérieures sur le nombre chromatique d’un graphe signé quand le graphe a peu de cycles. Enfin, nous étudions les relations entre les homomorphismes de graphes signés et le produit Cartésien des graphes signés.La deuxième famille de coloration consiste à colorer les arêtes au lieu des sommets en respectant différents critères. Nous étudions quatre types de colorations d’arêtes : la coloration d’arêtes « packing », la coloration d’arêtes injective, la coloration AVD et les 1-2-3-étiquetages. La coloration d’arêtes « packing » est une forme de coloration propre d’arêtes où chaque couleur a ses propres règles de conflits, par exemple, la couleur 1 pourrait obéir aux règles de la coloration propre d’arêtes tandis que la couleur 2 obéirait aux règles de la coloration forte d’arêtes. Nous étudions cette forme de coloration sur les graphes subcubiques en donnant des bornes supérieures sur le nombre de couleurs nécessaires pour colorer ces graphes. Une coloration d’arêtes injective est une coloration d’arêtes telle que pour chaque chemin de longueur 3, les deux arêtes aux extrémités du chemin n’ont pas la même couleur. Nous déterminons la complexité de la coloration d’arêtes injective sur plusieurs classes de graphes. Pour les colorations AVD, c’est-à-dire les colorations propres d’arêtes où les sommets adjacents sont incidents à des ensembles de couleurs différents, nous obtenons des bornes supérieures sur le nombre de couleurs requises pour colorer le graphe quand le degré maximum du graphe est significativement plus grand que son degré moyen maximum, ou quand le graphe est planaire et a un degré maximum supérieur ou égal à 12. Finalement, nous prouvons la 1-2-3 Conjecture multiplicative : pour tout graphe connexe (non réduit à une arête), on peut colorer ses arêtes avec les couleurs 1, 2 et 3 de telle manière que la coloration (de sommets) obtenue en associant à un sommet le produit des couleurs de ses arêtes incidentes est propre.