Contribution à l'étude de quelques problèmes de coloration de graphes

Abstract

Les problèmes de coloration sont au cœur de la théorie des graphes. Dans ce mémoire de thèse, nous nous intéressons essentiellement a deux types de colorations de graphes : les colorations d'incidences et les colorations orientées. Une incidence d'un graphe G est une paire (v, e) E V(G) x E(G) telle que v et e sont incidents. Deux incidences (v, e) et (w, f) sont adjacentes si l'une des conditions suivantes est satisfaite : (i) v = w, (ii) e = f ou (iii) l’arête vw est égale a e ou f . Une k-coloration d'incidence d'un graphe G est une application de l'ensemble des incidences de G dans un ensemble C de k couleurs telle que des couleurs distinctes sont affectées aux incidences adjacentes. Le nombre chromatique d'incidence de G est le plus petit entier k tel que G admet une k-coloration d'incidence. Une k-coloration orientée d'un graphe oriente G est une application c de l'ensemble des sommets V(G) de G vers l'ensemble de couleurs C = {1, 2, , k} telle que (i) si (x, y) est un arc de G alors c(x) c(y) et (ii) si (x, y) et (z, t) sont deux arcs de G tels que c(x) = c(t) alors c(y) c(z). Le nombre chromatique orienté d'un graphe orienté G est le plus petit entier k tel qu'il existe une k-coloration orientée de G. Nous étudions ces deux types de colorations pour différentes familles de graphes. En particulier, nous proposons différentes bornes pour : — le nombre chromatique d'incidence des graphes k-dégénérés, des graphes planaires, des graphes de degré moyen maximum borne et des graphes distances, — le nombre chromatique oriente des graphes d’excès k, des graphes planaires k-extérieurs, des graphes de Hahn et des graphes distances.