Cocoloration
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.
Comparaison
[modifier | modifier le code]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 sous-coloration (en) (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.
Historique
[modifier | modifier le code]La cocoloration a été nommée et étudiée pour la première fois par Lesniak et Straight (1977). Jørgensen (1995) caractérise des graphes trichromatiques critiques, tandis que Fomin, Kratsch et Novelli (2002) décrivent des algorithmes permettant d'approcher le nombre cochromatique d'un graphe. Zverovich (2000) 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.
Notes et références
[modifier | modifier le code]- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « cocoloring » (voir la liste des auteurs).
Bibliographie
[modifier | modifier le code]- Fedor V. Fomin, Dieter Kratsch et Jean-Christophe Novelli, « Approximating minimum cocolourings », Inf. Process. Lett., vol. 84, no 5, , p. 285–290 (DOI 10.1016/S0020-0190(02)00288-0).
- John Gimbel et H. Joseph Straight, « Some topics in cochromatic theory », Graphs and Combinatorics, vol. 3, no 1, , p. 255–265 (DOI 10.1007/BF01788548).
- Leif K. Jørgensen, « Critical 3-cochromatic graphs », Graphs and Combinatorics, vol. 11, no 3, , p. 263–266 (DOI 10.1007/BF01793013).
- L. Lesniak et H. J. Straight, « The cochromatic number of a graph », Ars Combinatoria, vol. 3, , p. 39–46.
- H. J. Straight, « Cochromatic number and the genus of a graph », Journal of Graph Theory, vol. 3, no 1, , p. 43–51 (DOI 10.1002/jgt.3190030106).
- Igor V. Zverovich, « Perfect cochromatic graphs », Research report, Rutgers University Center for Operations Research, no RRR 16-2000, (lire en ligne [archive du ], consulté le ).
