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)$ […]
Coloration de Wigderson
- Auteur de la publication Par Xavier BADIN de MONTJOYE
- Date de publication
- Catégories Dans Approximation, Exercices