Editing Cocoloring (section)

[[Image:Cocoloring.svg|400px|right|thumb|Cocoloring with 3 colors (upper left figure):
a [[Graph_coloring#Vertex_coloring|proper]] 3-coloring of this graph is impossible.
The blue [[Glossary of graph theory#Subgraphs|subgraph]] forms a [[Clique (graph theory)|clique]] (bottom right figure),
while the red and green subgraphs form cliques on the graph's [[Glossary of graph theory#Basics|complement]]. ]]

In [[graph theory]], a '''cocoloring''' of a graph ''G'' is an assignment of [[color]]s to the vertices such that each color class forms an [[Independent set (graph theory)|independent set]] in ''G'' or in the [[Glossary of graph theory#Basics|complement]] of ''G''. The '''cochromatic number''' z(''G'') of ''G'' is the fewest colors needed in any cocolorings of ''G''. The graphs with cochromatic number 2 are exactly the [[bipartite graph]]s, complements of bipartite graphs, and [[split graph]]s.

As the requirement that each color class be a clique or independent is weaker than the requirement for [[Graph coloring|coloring]] (in which each color class must be an independent set) and stronger than for [[subcoloring]] (in which each color class must be a disjoint union of cliques), it follows that the cochromatic number of ''G'' is less than or equal to the [[chromatic number]] of ''G'', and that it is greater than or equal to the subchromatic number of ''G''.

Cocoloring was named and first studied by {{harvtxt|Lesniak|Straight|1977}}. {{harvtxt|Jørgensen|1995}} characterizes critical 3-cochromatic graphs, while {{harvtxt|Fomin|Kratsch|Novelli|2002}} describe algorithms for approximating the cochromatic number of a graph. {{harvtxt|Zverovich|2000}} defines a class of ''perfect cochromatic graphs'', analogous to the definition of perfect graphs via graph coloring, and provides a forbidden subgraph characterization of these graphs.