出典:Wiktionary
出典:Wikipedia
出典:『Wikipedia』 (2010/04/18 00:06 UTC 版)
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.