Exercice
Le but de cet exercice est de colorer un graphe que l’on sait $3$-coloriable en utilisant le moins de couleurs possible.
$1)$ Soit un graphe $G$ quelconque de degré maximal $\Delta$. Donner une borne sur le nombre chromatique de $G$.
Soit $G$ un graphe $3$-coloriable. Pour $u$ un sommet de $G$, on note $N(u)$ l’ensemble des voisins de $u$.
$2)$ Montrer qu’on peut colorier avec $3$ couleurs en temps polynomial le sous-graphe induit par $\{u\} \bigcup N(u)$.
$3)$ En déduire un algorithme qui tourne en temps polynomial pour colorier un graphe $3$-coloriable de $n$ sommets avec $3\sqrt{n}$ couleurs.
Correction
$1.$ On propose l’algorithme suivant : on colorie chaque sommet un par un en lui attribuant la plus petite couleur non attribué à un de ses voisins. De ce fait, chaque sommet a une couleur inférieur ou égale au nombre de ses voisins plus un. Ainsi, pour un graphe $G$ de degré maximal $\Delta$, son nombre chromatique est borné par $\Delta + 1$.
On note que dans le cas du graphe complet, cette borne est atteinte. Il s’agit donc de la meilleure borne possible.
$2.$ On attribue à $u$ la couleur $1$. De plus, comme $G$ est $3$-coloriable, cela signifie que l’ensemble de ses voisins forme un graphe bipartie. Or $2$-colorier un graphe bipartie est faisable par un simple parcours. On a donc colorié notre sous-graphe avec trois couleurs en un temps polynomial.
$3.$ Soit $n$ le nombre de sommets de notre graphe. On propose l’algorithme récursif suivant : on cherche le sommet $s$ de degré maximal. Si ce degré est strictement inférieur à $\sqrt{n}$ on peut colorier le graphe avec $\sqrt{n}$ couleurs. Sinon, on considère ses voisins qui forment donc un graphe bipartie. On les colorie avec $2$ couleurs qu’on ne réutilisera plus. On supprime les sommets coloriés du graphe et on recommence. On effectue au plus $\sqrt{n}$ passage dans la boucle. Dans chaque passage, on utilise $2$ nouvelles couleurs, soit $2\sqrt{n}$ au total. Enfin, on passe au plus une fois dans le cas où on colorie utilisant $\sqrt{n}$ couleurs.
Notre algorithme permet donc bien de colorier un graphe $3$-coloriable avec $3\sqrt{n}$ couleurs.
Cette approximation a été proposée par Wigderson. Khanna, Linial et Saffra ont montré en 1993 que le problème de colorier un graphe qu’on sait $3$-coloriable avec $4$ couleurs est NP-difficile.