En teoría de grafos , una cocoloración de un grafo G es una asignación de colores a los vértices de modo que cada clase de color forme un conjunto independiente en G o en el complemento de G. El número cocromático z( G ) de G es la menor cantidad de colores necesarios en cualquier cocoloración de G. Los grafos con número cocromático 2 son exactamente los grafos bipartitos , los complementos de grafos bipartitos y los grafos divididos .
Como el requisito de que cada clase de color sea una camarilla o independiente es más débil que el requisito de coloración (en el que cada clase de color debe ser un conjunto independiente) y más fuerte que el de subcoloración (en el que cada clase de color debe ser una unión disjunta de camarillas), se deduce que el número cocromático de G es menor o igual que el número cromático de G , y que es mayor o igual que el número subcromático de G .
La cocoloración fue nombrada y estudiada por primera vez por Lesniak y Straight (1977). Jørgensen (1995) caracteriza los grafos 3-cocromáticos críticos, mientras que Fomin, Kratsch y Novelli (2002) describen algoritmos para aproximar el número cocromático de un grafo. Zverovich (2000) define una clase de grafos cocromáticos perfectos , análoga a la definición de grafos perfectos a través de la coloración de grafos, y proporciona una caracterización de subgrafos prohibidos de estos grafos.