Nombre achromatique

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

En théorie des graphes, une coloration complète est l'opposé d'une coloration harmonieuse en ce sens que c'est une coloration des sommets dans laquelle toute paire de couleurs apparait au moins sur une paire de sommets adjacents. Le nombre achromatique ψ(G) d'une graphe G est le nombre maximum de couleurs possibles dans une coloration complète de G. Trouver ψ(G) est un problème d'optimisation. Le problème de décision pour le problème de coloration complète peut être exprimé ainsi :

INSTANCE: un graphe

G = (S, A)

et un entier positif

k

QUESTION: existe-t-il une partition de

S

en au plus

k

ensembles disjoints $S_1,S_2,\ldots,S_k$ telle que chaque

S i

est un ensemble indépendant pour

G

et telle que pour chaque paire d'ensembles distincts $S_i,S_j,S_i \cup S_j$ ne soit pas un ensemble indépendant.

Déterminer le nombre achromatiques est NP-difficile ; déterminer s'il est inférieur à un nombre donné est NP-complet, comme l'ont montré Yannakakis et Gavril en 1978 par une transformation depuis le problème minimum maximal matching. Le problème reste NP-complet même si on le restreint aux graphes qui sont le complément d'un graphe biparti (c’est-à-dire d'un graphe qui n'a pas d'ensemble indépendant de plus de deux sommets).

Le problème d'optimisation est approximable en $O\left(|S|/\sqrt{\log |S|}\right)$

[modifier] Réferences

Michael R. Garey et David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979. ISBN 0-7167-1045-5}} A1.1: GT2, pg.190.