Processing math: 100%

$\newcommand{\eps}{\varepsilon} \newcommand{\RR}{\mathbb{R}} \newcommand{\rd}{\operatorname{d}} \newcommand{\set}[1]{\left\{#1\right\}}$

Catégorie : Approximation

Coloration de Wigderson

Auteur de la publication Par Xavier BADIN de MONTJOYE
Date de publication 11 juillet 2021
Catégories Dans Approximation, Exercices
Aucun commentaire sur Coloration de Wigderson

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)$ […]