Coloration de graphe

Problème d’assigner des couleurs aux sommets d’un graphe tel que deux sommets adjacents aient des couleurs différentes.

Problème de décision (COLOR)

• Instance : Graphe G=(V,E)G=(V,E) G=(V,E) et entier kk k
• Question : Peut-on colorier GG G avec au plus kk k couleurs ?

Complexité

COLOR est NP-complet pour $k\ge 3$.

Certificat

• Certificat de verification : Fonction $c:V\to \{1,...,k\}$
• Vérification : Vérifier que $\forall xy\in E,c(x)\ne c(y)$

Cas particulier

• 2-COLOR est dans Classe P (vérifier si le graphe est biparti)
• 3-COLOR est NP-complet

Self-réductibilité

COLOR est self-réductible.

Algorithme avec oracle

colordec(G, k) -> oui/non  // oracle O(1)

Idée : Déterminer si deux sommets peuvent avoir la même couleur
      en ajoutant une arête entre eux et vérifiant si le graphe
      reste k-coloriable

Réduction depuis 3-Coloration Planaire

$\text{3CP}{\ll }_P\text{3-COLOR}$

Transformation : Ajouter des arêtes entre sommets qui n’ont pas la même couleur dans la coloration planaire.