Cocoloring
（重定向自Cochromatic number）
![Cocoloring with 3 colors (upper left figure):
a proper 3-coloring of this graph is impossible.
The blue subgraph forms a clique (bottom right figure),
while the red and green subgraphs form cliques on the graph's complement.](/Images/godic/202501/05/Cocoloring.svg5616.png")
In graph theory, a cocoloring of a graph G is an assignment of colors to the vertices such that each color class forms an independent set in G or in the complement of G. The cochromatic number z(G) of G is the least number of colors needed in any cocolorings of G. The graphs with cochromatic number 2 are exactly the bipartite graphs, complements of bipartite graphs, and split graphs.