Em teoria dos grafos , um Cocoloring de um grafo G é uma atribuição de cores para os vértices de modo que cada classe cor formas um conjunto independente em G ou o grafo complementar de G . O número cochromatique z ( L ) de L é o menor número de cores necessárias num Cocoloring de L . Os gráficos do número 2 cocromático são exatamente gráficos bipartidos , complementos de gráficos bipartidos e gráficos divididos .
A condição de que cada classe de cor seja um clique ou um conjunto independente é mais fraca do que a condição de coloração (onde cada classe de cor deve ser um conjunto independente) e é mais forte do que para sub-coloração (em) (onde cada classe de cor deve ser uma união disjunta de cliques); segue-se que o número cocromático de G é menor ou igual ao número cromático de G e é maior ou igual ao número de G subcromático .
A co-coloração foi nomeada e estudada pela primeira vez por Lesniak e Straight (1977) . Jørgensen (1995) caracteriza grafos tricromáticos críticos, enquanto Fomin, Kratsch e Novelli (2002) descrevem algoritmos para aproximar o número cocromático de um grafo. Zverovich (2000) define uma classe de grafos cocromáticos perfeitos , análoga à definição de grafos perfeitos por meio da coloração de grafos, e fornece uma caracterização de subgráfico proibida desses grafos.