В теории графов ко -раскраска графа G — это такое назначение цветов вершинам, что каждый цветовой класс образует независимое множество в G или в дополнении к G. Ко -хроматическое число z( G ) графа G — это наименьшее количество цветов, необходимое для любой ко-раскраски графа G. Графы с ко-хроматическим числом 2 — это в точности двудольные графы , дополнения двудольных графов и расщепленные графы .
Поскольку требование, чтобы каждый цветовой класс был кликой или независимым, слабее, чем требование для раскраски (в котором каждый цветовой класс должен быть независимым множеством) и сильнее, чем требование для подраскраски (в котором каждый цветовой класс должен быть несвязным объединением клик), отсюда следует, что кохроматическое число G меньше или равно хроматическому числу G и что оно больше или равно субхроматическому числу G.
Cocoloring был назван и впервые изучен Lesniak & Straight (1977). Jørgensen (1995) характеризует критические 3-кохроматические графы, в то время как Fomin, Kratsch & Novelli (2002) описывают алгоритмы для аппроксимации кохроматического числа графа. Zverovich (2000) определяет класс совершенных кохроматических графов , аналогичный определению совершенных графов через раскраску графа, и предоставляет характеристику запрещенных подграфов этих графов.