Nombre achromatique

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

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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'un graphe G est le nombre maximum de couleurs possibles dans une coloration complète de G.

Coloration complète du graphe de Clebsch avec 8 couleurs.

Exemple

Dans la figure ci-contre, on a réussi à colorier le graphe de Clebsch avec huit couleurs, de manière que chaque paire de couleurs apparaisse sur au moins une arête. On ne peut pas avoir de coloration complète avec plus de couleurs : dans toute coloration à neuf couleurs, une des couleurs n'apparaîtrait que sur un des sommets, et il n'y aurait donc pas assez d'arêtes incidentes pour avoir toutes les paires de couleurs contenant cette couleur. Le nombre achromatique de ce graphe est donc 8.

Calcul du nombre achromatique

Définition du problème algorithmique

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 ) {\displaystyle G=(S,A)} et un entier positif k {\displaystyle k}
QUESTION : existe-t-il une partition de S {\displaystyle S} en au plus k {\displaystyle k} ensembles S 1 , S 2 , … , S k {\displaystyle S_{1},S_{2},\ldots ,S_{k}} disjoints deux à deux, telle que chaque S i {\displaystyle S_{i}} soit un ensemble indépendant pour G {\displaystyle G} et telle que pour chaque paire d'ensembles distincts S i , S j , S i ∪ S j {\displaystyle S_{i},S_{j},S_{i}\cup S_{j}} ne soit pas un ensemble indépendant.

NP-complétude

Déterminer le nombre achromatique est NP-difficile ; déterminer s'il est supé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).

Approximation

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

Références

  • 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.

Liens externes

  • (en) Un condensé de problèmes d'optimisation dans NP
  • (en) www.maths.dundee.ac.uk A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards
  • icône décorative Portail de l'informatique théorique