Nombre chromatique de sommets de graphes

Ensemble stable ou indépendant 

Soit G = (X, E) un graphe simple. Un sous ensemble S de X est dit stable si deux sommets quelconques de S sont non adjacents Définition 2 Soit G = (X , E) un graphe simple et S X est dit stable si ΓG (S) ח S = Ø Exemple 1 Dans le graphique G les ensembles {1,5}, {5,6} {6,4,3}, etc. sont des ensembles stables Pour chacun de ces ensembles, aucune arête ne relie deux de ses sommets Conséquence Il est clair que tout sous-ensemble d’un ensemble stable est stable. Il est alors naturel de rechercher le cardinal maximum d’un ensemble stable. Définition 3 Soit G = (X , E) un graphe simple et S l’ensemble des ensembles stables. Le nombre α (G) tel que α (G) = max {card ( S )} est appelé nombre stable ou degré de stabilité de G C’est le nombre maximal de sommets constituant un ensemble stable.

Exemple 2 L’ensemble {1 ; 3 ; 7} est stable aucune arête ne relie deux de ses points. Ici il est immédiat que c’est un stable maximum, car les trois cliques {1 ; 2 ; 5 }, {6 ; 7 } et {3 ; 4} partitionnent l’ensemble des sommets, et un stable ne pouvant avoir plus d’un point dans chacune de ces trois cliques, son cardinal doit être Inférieur ou égal à 3. On a donc α (G) = 3. En général, il assez difficile de vérifier sans ordinateur qu’un stable donné est de cardinal maximum. La connaissance des degrés des sommets d’un graphe nous permet d’énoncer certains résultats sur le nombre stabilité.

Majoration et Minoration

Dans ce paragraphe nous nous proposons d’étudier des bornes pour le nombre de stabilité en fonction des degrés ou du nombre d’arêtes Théorème 1 (Meyer 1972). Soit G = (X , E) un graphe simple d’ordre n sans sommets isolés, ses sommets x1, x2…., xn étant indexés de sorte que dG (x1) ≤ dG (x2) ≤………≤ dG (xn) si, pour un entier p, 2 ≤ p ≤ n, alors on a dG (xn) +………+ dG (xn – p +2) ≤ n – p Démonstration Pour démontrer ce résultat, raisonnons par récurrence sur p Si p = 2 et si dG (xn) ≤ n – 2, alors pour tout x Є X, dG (x) < n – 1 et il existe un point y Є X non relié à x, et l’ensemble {x, y} est un stable dans de deux sommets. Si ce résultat est vérifié pour p, montrons qu’il l’est encore pour p+1 34 supposons que l’on ait dG (xn) +…….+ dG (xn – p+1) ≤ n – p – 1< n –1.

En vertu de l’hypothèse de récurrence, un ensemble stable de moins de p sommets est inclus dans un ensemble stable So de p sommets. Posons S0 = {y1,…..yp} on a : dG (y1) + … + dG (yp) ≤ dG (xn) + … + dG (xn – p+1) ≤ n-p-1 Par suite, il existe au moins un point a dans X-S0 qui n’est relié à aucun point de S0. Alors S0 U {a} est un stable de p+1 sommets contenant S. Le théorème suivant donne, pour les graphes d’ordre donné et le nombre de stabilité fixé. Le nombre minimum d’arêtes possible. Théorème 2 (Turan 1941) Soit n et k deux entiers tels que n ≥ k ≥ 0 n – 1 q = + 1 de sorte que n = k (q – 1) + r, ou 0 < r ≤ k k Soit Gn, k le graphe simple formé en prenant k cliques disjointes, r d’entre elles ayant q sommets, les k – r autres, q – 1 sommets.

Si G est un graphe d’ordre n et de nombre de stabilité au plus k, on a m (G) ≥ m (Gn, k), En outre, on a l’égalité si et seulement si G est isomorphe à Gn, k) Corollaire 1 Si un graphe simple G a n sommets, m arêtes, et si α (G) = k, on a n – 1 m ≥ (q – 1) (n – k q) ou q = + 1 2 k En outre, on a l’égalité si et seulement si G est identique au graphe Gn, k défini plus haut. Démonstration En effet, le graphe Gn, k est composé de r cliques de q sommets et de (k – r) cliques de q – 1 sommets. Donc le nombre de ses arêtes est d’après le théorème (hand….) q (q – 1) (q – 1) (q – 2) m (Gn, k) = r + (k – r ) 2 2 q – 1 (r q +k q – r q – 2 k + 2 r) = 2 (q-1) ( n – k+ r) = 2 m (Gn, k) = 1 (q – 1) (n – k + n – k ( q – 1) ) 2 = (q – 1) (n – k q) 35 2 Corollaire 2 Si G est un graphe simple avec n sommets et m arêtes, on a n² α (G) ≥ 2 m + n on a l’égalité si et seulement si toutes les composantes connexes de G sont des cliques de même cardinalité.

Démonstration

En effet d’après le corollaire 1, on a, en posant α(G) = k , n = k (q – 1) + r 1 1 m ≥ (q – 1) (n – k + r) = (n – r) (n – k + r) 2 2 k Comme le minimum du second membre pour r Є [1 ; k] est obtenu avec r = k 2 k m ≥ (n – k ) n n ² d’ou k ≥ 2 m + n 2) si G consiste en p cliques de cardinalité n0 , on a α (G) = p et n² p² n0² = = p = α (G) 2 m + n pn0 (n0 –1) + pn0 On a donc bien l’égalité dans la relation de l’énoncé. Inversement, si on a l’égalité, on doit avoir G = Gn, k et en plus r = k donc G a bien la forme indiquée par l’énoncé.