3-Clique Partition pour les graphiques de diamètre fixe

Le problème de la partition à 3 cliques est le problème de déterminer si les sommets d'un graphe, disons , peuvent être partitionnés en 3 cliques. Ce problème est NP-difficile par une simple réduction du problème de la colorabilité 3. Il n'est pas difficile de voir que la réponse à ce problème est facile lorsque diam ( G ) = 1 ou diam ( G ) > 5 . Le problème reste NP-difficile lorsque diam ( G ) = 2 par une simple réduction de lui-même (étant donné un graphe G , ajoutez un sommet et connectez-le à tous les autres sommets).$G$$\textrm{diam}(G) = 1$$\textrm{diam}(G) > 5$$\textrm{diam}(G) = 2$$G$

Quelle est la complexité de ce problème pour les graphes avec pour 3 ≤ p ≤ 5 ?$\textrm{diam}(G) = p$$3\le p \le 5$

Le problème semble être dans .$P$

Prenez deux sommets , v avec une distance exactement de 3 (une telle paire doit exister lorsque p ≥ 3 ). Ils doivent avoir des couleurs différentes (j'utiliserai R, G, B pour désigner 3 couleurs et les sommets de la même clique sont colorés de la même couleur). Wlog suppose que u est de couleur rouge et v est de couleur verte.$u$$v$$p\ge 3$$u$$v$

Maintenant, le reste des sommets est partitionné en 3 ensembles: (voisins de u ), Γ ( v ) et V - Γ ( u ) - Γ ( v ) . Le troisième ensemble doit être coloré en bleu car ils ne sont adjacents ni à u ni à v . Les voisins de u doivent être de couleur rouge ou bleue car ils ne sont pas adjacents à v , de même que les voisins de $\Gamma(u)$$u$$\Gamma(v)$$V-\Gamma(u)-\Gamma(v)$$u$$v$$u$$v$$v$doit être de couleur verte ou bleue. Chaque sommet a maintenant au maximum deux choix, donc le problème devient une instance 2-SAT que nous pouvons résoudre en temps polynomial.