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.

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.

Comparaison

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

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

    Bibliographie
    • 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 ).
    • Portail des mathématiques
    • Portail de l'informatique théorique
    Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.