WikiDer > Покраска

Раскраска 3 красками (верхний левый рисунок): а правильный 3-раскраска этого графа невозможна. Синий подграф образует клика (нижний правый рисунок), а красный и зеленый подграфы образуют клики на дополнять.

В теория графов, а колорирование графа г это задание цвета к вершинам, так что каждый цветовой класс образует независимый набор в г или в дополнять из г. В кохроматическое число z (г) из г это наименьшее количество цветов, необходимых в любых соцветиях г. Графики с кохроматическим числом 2 в точности соответствуют двудольные графы, дополнения к двудольным графам и разделить графики.

Поскольку требование, чтобы каждый цветовой класс был кликой или независимым, слабее, чем требование для раскраска (в котором каждый цветовой класс должен быть независимым набором) и сильнее, чем для подкрашивание (в котором каждый цветовой класс должен быть непересекающимся объединением клик), отсюда следует, что кохроматическое число г меньше или равно хроматическое число из г, и что оно больше или равно субхроматическому числу г.

Колоринг был назван и впервые изучен Лесняк и Straight (1977). Йоргенсен (1995) характеризует критические 3-кохроматические графы, а Фомин, Крач и Новелли (2002) описывают алгоритмы аппроксимации кохроматического числа графа. Зверович (2000) определяет класс идеальные кохроматические графы, аналогично определению идеальных графов с помощью раскраски графов, и обеспечивает характеристику запрещенных подграфов этих графов.

использованная литература