Coloriage de graphe

Si tu avais une preuve de ce que tu annonces, tu pourrais la transformer facilement en un algorithme : on n'y est pas.

Pour commencer, il me semble que l'idée « on ajoute un sommet qui fait augmenter le degré maximal » est étrange une erreur. On suppose la propriété vraie pour tout graphe à $n-1$ sommets, on se donne un graphe à $n$ sommets de degré maximal $\Delta$. Il est très possible que plusieurs, voire tous les sommets aient pour degré $\Delta$. Je ne vois pas alors quel est ce fameux sommet « qui fait augmenter la valeur de $\Delta$ » dont tu parles.

Pour l'hérédité, donc, la donnée est un graphe à $n$ sommets et on suppose que le degré est $\Delta$. On choisit un sommet, disons $s$, il est sans doute habile de le choisir de degré maximal. On considère le graphe $H$ obtenu en supprimant $s$ et les arêtes incidentes. Et alors ? Que peux-tu dire du degré maximal des sommets de $H$ ?

Certes. Je pense qu'il faudrait être plus précis, genre distinguer le cas où le degré maximal est inchangé après suppression de $s$ et le cas où le degré maximal baisse (de combien au fait ?).

Je ne comprends pas tes histoires de passer de $n$ à $n-1$ ou de $n-1$ à $n$. On ne passe rien du tout. On se donne un entier $n$ et on fait l'hypothèse suivante :

Hypothèse de récurrence a écrit:

Pour tout graphe à $n-1$ sommet de degré maximal $d$, on peut trouver une fonction de coloriage à $d+1$ couleurs au plus.

On veut à présent prouver l'énoncé correspondant pour un graphe à $n$ sommets. On commence donc par fixer un graphe $\Gamma$ à $n$ sommets. On appelle $\Delta$ le maximum des degrés des sommets. (Ce n'est pas une bonne idée de le noter $\Delta_n$ parce qu'il dépend du graphe $\Gamma$, pas seulement de $n$.)

Ce qu'on doit faire ? Trouver une fonction de coloriage sur ce graphe. Comment faire ? Probablement exhiber un sous-graphe à $n-1$ sommets pour pouvoir utiliser l'hypothèse de récurrence. Ce serait bien parce que ça permettrait de colorier presque tous les sommets, quitte à changer quelques couleurs si nécessaire.

Bon, il faut donc choisir $n-1$ sommets de $\Gamma$ de façon habile. Comme l'histoire parle de degré maximal des sommets, on en choisit un, $s$ et on considère le graphe $\Gamma'$ dont les sommets sont ceux de $\Gamma$ qui sont différents de $s$ et les arêtes, celles de $\Gamma$ qui ne contiennent pas $s$. On appelle $\Delta'$ le degré maximal des sommets. (Ce n'est pas une bonne idée de le noter $\Delta_n$ parce qu'il dépend du graphe $\Gamma'$, c'est-à-dire de $\Gamma$ et de $s$ et pas seulement de $n$.) Comme on a enlevé au plus une arête par sommet $s'$ (celle qui relie éventuellement $s'$ à $s$ dans $\Gamma$), on peut affirmer que $\Delta'$ vaut $\Delta$ ou $\Delta-1$. (Ce dernier cas arrive quand $s$ est connecté à tous les sommets de degré $\Delta$ – pas nécessairement à tous les sommets.)

Est-ce qu'on a fini ? Est-ce qu'on a exhibé une façon de colorier $\Gamma$ ? Eh bien, visiblement, non. Il faut donc travailler encore (enfin, commencer à travailler).

En tout cas, grâce à l'hypothèse de récurrence, on peut produire un coloriage de $\Gamma'$ en $\Delta'+1$ couleurs. Ce qu'il reste à faire ? Trouver une couleur pour le dernier sommet $s$. Est-ce possible ?

Ce que je te proposais, c'était de distinguer deux cas selon que $\Delta'=\Delta-1$ ou $\Delta'=\Delta$. En y réfléchissant mieux, ça n'a pas l'air nécessaire. Il n'y a plus qu'un argument à donner.

Comme dit Claude, j'ai dit une grosse bêtise : $\Delta'\le\Delta$ et on ne peut pas dire plus.

Pour compléter le coloriage de $\Gamma'$ en un coloriage de $\Gamma$ : $s$ n'est connecté qu'à $\Delta$ sommets au plus donc avec $\Delta+1$ couleurs, on peut en trouver une qui ne figure pas parmi les couleurs de ces sommets (reliés à $s$). Ça permet de terminer la preuve de l'hérédité et donc la récurrence. Comme tu vois, cette preuve est essentiellement un algorithme.

D'après ce message et le suivant, je pense que tu as compris (pour autant que j'aie compris moi-même).

Si on complète le coloriage comme tu l'as fait, sans modifier de couleur, il nous faut au moins $\Delta'+1$ couleurs pour le petit graphe $\Gamma'$ (du moins, on ne peut pas s'en sortir avec moins de couleurs en utilisant seulement l'hypothèse de récurrence) et $\deg(s)+1$ couleurs pour compléter le coloriage ($\deg(s)+1$ et pas $\deg(s)$ parce que rien n'empêche les $\deg(s)$ voisins de $s$ d'avoir des couleurs différentes : par exemple, ils pourraient être tous reliés entre eux). On peut peut-être faire mieux mais sans argument supplémentaire, on ne peut pas affirmer l'existence d'un coloriage avec moins de $\max(\Delta'+1,\deg(s)+1)$ couleurs. Par définition du degré maximal, on sait que $\Delta'\le\Delta$ et que $\deg(s)\le\Delta$ mais comme il peut y avoir égalité, on ne peut pas garantir de pouvoir faire mieux que $\Delta+1$ couleurs. (Au passage, le choix de $s$ était sans importance, même si j'avais proposé de le prendre de degré maximal.)

Autrement dit, on a vérifié qu'un graphe de degré maximal $\Delta$ peut être colorié avec $\Delta+1$ couleurs mais on ne peut pas garantir mieux.

Ce n'est pas la preuve qui est en cause. En effet, le constat suivant, c'est que pour tout entier $n$ et le graphe complet à $n$ sommets (pour lequel $\Delta=n-1$), il faut au moins $n$ couleurs (et $n=\Delta+1$). Autrement dit, si $\Delta$ est un entier et si $f(\Delta)<\Delta+1$, le graphe complet sur $\Delta+1$ sommets ne peut pas être colorié avec $f(\Delta)$ couleurs. Cela veut dire que dans une assertion du type : « tout graphe de degré maximal $\Delta$ peut être colorié avec $f(\Delta)$ couleurs », la meilleure borne $f(\Delta)$ est $\Delta+1$.