Bonsoir,

J'ai l'exercice suivant en théorie des graphes:

Soit \(\overline{G}\)=(V, \(\overline{E}\)), le complémentaire d'un graphe G = (V,E), \(\gamma(G)\), le nombre chromatique du graphe G, d'ordre n\(\in\mathbb{N}\). Montrer les inégalités suivantes:

\(\gamma(G)+\gamma(\overline{G})\leq n\) et \(\gamma(G).\gamma(\overline{G})\geq n\)

J'ai tout essayé mais rien n'a marché. Pour la première inégalité par exemple, puisqu'il revient à montrer que \(\gamma(G)\leq n-\gamma(\overline{G})\), j'ai pensé ainsi: il suffit de considérer une partie stable de V, de cardinal \(\gamma(\overline{G}\)), de colorier le sommets de cette partie avec des couleurs toutes distinctes et ensuite, de colorier les \(n-\gamma(\overline{G})\) sommets restants, tous de la même couleur. On a ainsi le résultat cherché. Mais ce raisonnement tient seulement si on est toujours sur que \(\gamma(\overline{G})\leq\alpha(G)\)

Voilà, si vous avez ne serait-ce que des pistes de solutions pour ces inégalités, je suis preneur

Merci d'avance

-
Edité par Dr_strange 26 juin 2018 à 20:47:43

Bonjour,

As-tu essayé l'induction ? Ca me parraît faisable dans cette direction.

Pour ton raisonnement, j'avoue ne pas comprendre comment tu arrives à "on a ainsi le résultat cherché". Il faudrait être plus clair.

EDIT:

En fait es-tu certain que c'est <= n ? (n+1 à l'air de fonctionner)

Parce que dans le cas particulier d'un graphe de 2 sommets, il faut 3 couleurs au minimum (2 pour le graphe contenant l'unique arête et 1 pour l'autre).

-
Edité par Anonyme 27 juin 2018 à 13:51:39

Bonjour Erylanor, 

Concernant mon raisonnement,  je me suis emmêlé les pinceaux:

Je cherche à majorer le nombre chromatiques graphe G. Je part de la définition du nombre chromatique d'un graphe: "nombre minimale de couleurs nécessaires au coloriage des sommets d'un graphe de sorte que deux sommets voisins soient de couleurs distinctes" 

Si on considère une partie stable du graphe G de cardinal \( \gamma(\overline{G})\) et qu'on colorie tous les sommets de cette partie avec la même couleur pour ensuite colorier les \( n-\gamma(\overline{G})\) sommets restant de couleurs toutes diffèrentes, on aura \( \gamma(G) \leq 1 + (n-\gamma(\overline{G}))\)

Concernant le raisonnement par induction sur n, je ne vois pas trop. J'ai du mal déjà avec le cas où n=1

Quant à votre remarque en EDIT, dans l'exercice, c'est bien <=n 

Quand vous dites n+1 à l'air de fonctionner, que voulez-vous dire ?

-
Edité par Dr_strange 27 juin 2018 à 18:17:20

Disons que le problème que je vois, c'est que dans le cas particulier d'un graphe à 1 seul sommet, l'énoncé est faux car il faut une couleur pour colorier chaque graphe. On doit alors montrer que 1+1<=1.

Ou bien alors il y a quelque chose que j'ai fondamentalement loupé dans l'énoncé.

Dans le cas n=1, il y a un problème, donc pas la peine de chercher plus loin, l'énoncé est erroné.

En revanche, si c'est n+1 au lieu de n je pense avoir une solution.

Pour l'autre, je n'ai pas encore trouvé (pas trop cherché non plus en fait).

D'ailleurs, qu'est-ce que le nombre de stabilité ? Je ne me souviens plus de toutes les définitions...

Le nombre de stabilité d'un graphe est le cardinal de la plus grande partie stable de ce graphe.

Une partie stable d'un graphe G = (V,E) est un sous-ensemble de V, constitué de sommets non adjacents deux à deux.

suggestion: pour la seconde inégalité, on peut partir de la propriété suivante:

une coloration en \(q\) couleurs implique  une partition de  \(V\)  en \(q\) parties stables \((S_1,...,S_q)\).
On applique pour le nombre chromatique \(q=\gamma(G)\) qui est, de sa définition,  le plus petit nombre \(q\) pouvant réaliser cette partition..

Donc \(n= \sum_{i=1}^{\gamma(G)}\vert S_i \vert\). Mais nécessairement  \(\vert S_i \vert \leq \alpha(G)), \forall i\) .

Alors \(n\leq   \gamma(G) \alpha(G)   \)

Mais on  a   \( \alpha(G) \leq \gamma(\overline{G})\)  qui est vraie pour tout graphe à mon avis ( c'est l'inverse de l'inégalité que tu as supposé  dans ton premier post qui ne serait   en fait jamais vraie  ! ).

En effet , il me semble que  si \(\alpha(G)\) est le cardinal de la plus grande partie stable  \(S\) de \(G\), \(S\) est une clique de \(\overline{G}\) (donc un sous-graphe complet), qui nécessite donc \(\alpha(G)\)  couleurs,  donc le nombre chromatique de  \(\overline{G}\) est nécessairement supérieur ou égal à \(\alpha(G)\)

 ce qui implique alors l'inégalité attendue  \(   \gamma(G) \gamma(\overline{G}) \geq n  \)

-
Edité par Sennacherib 28 juin 2018 à 12:35:23

Sennacherib a écrit:

Mais on  a   \( \alpha(G) \leq \gamma(\overline{G})\)  qui est vraie pour tout graphe à mon avis ( c'est l'inverse de l'inégalité que tu as supposé  dans ton premier post qui est  en fait jamais vraie  ! ).

L'inégalité du premier post est vraie dans le cas particulier de l'égalité (mais je chipote)

Sinon je suis d'accord avec le raisonnement.

-
Edité par Anonyme 28 juin 2018 à 12:27:35

Merci à vous deux 

Sennacherib je me suis un peu emmêlé les pinceaux car je travaillais sous pression. En effets avec votre inégalité, sachant que j'avais la méthode pour arriver à montrer que \(\gamma(G)\alpha(G)\geq n\), j'ai pu arriver au résultat. 

Merci encore