Cocoloración

En teoría de grafos , una cocoloración de un grafo G es una asignación de colores a los vértices tal que cada clase de color forma un conjunto independiente en G o en el complemento de G. El número cocromático z( G ) de G es el número mínimo de colores necesarios en cualquier cocoloración de G. Los grafos con número cocromático 2 son precisamente 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 para la coloración (en la que cada clase de color debe ser un conjunto independiente) y más fuerte que para la subcoloración (en la 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.

El concepto de cocoloración fue denominado y estudiado 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 mediante coloración de grafos, y proporciona una caracterización de subgrafos prohibidos para estos grafos.