Cocoloration

droite|vignette|400x400px| Cocoloration avec 3 couleurs (figure en haut à gauche) : une 3-coloration propre de ce graphe est impossible. Le sous-graphe bleu forme une clique (figure en bas à droite), tandis que les sous-graphes rouge et vert forment des cliques du graphe complémentaire. En théorie des graphes, une cocoloration d'un graphe G est une affectation de couleurs aux sommets de telle sorte que chaque classe de couleur forme un ensemble indépendant dans G ou dans le graphe complémentaire de G. Le nombre cochromatique z( G ) de G est le plus petit nombre de couleurs nécessaires dans une cocoloration de G. Les graphes de nombre cochromatique 2 sont exactement les graphes bipartis, les compléments des graphes bipartis et les graphes divisés. La condition que chaque classe de couleur est une clique ou est un ensemble indépendant est plus faible que la condition de la coloration (où chaque classe de couleur doit être un ensemble indépendant) et est plus forte que pour la (où chaque classe de couleur doit être une union disjointe de cliques) ; il s'ensuit que le nombre cochromatique de G est inférieur ou égal au nombre chromatique de G, et qu'il est supérieur ou égal au nombre sous-chromatique de G. La cocoloration a été nommée et étudiée pour la première fois par . caractérise des graphes trichromatiques critiques, tandis que décrivent des algorithmes permettant d'approcher le nombre cochromatique d'un graphe. définit une classe de graphes cochromatiques parfaits, analogue à la définition de graphes parfaits via la coloration de graphes, et fournit une caractérisation de sous-graphe interdite de ces graphes.