W teorii wykres , A Cocoloring grafu G jest przyporządkowanie kolorów na siebie tak, że kolor klasy tworzy wierzchołki niezależnego zestawu w G lub wykres dopełniacza o G . Liczba cochromatique z ( G ) z G jest najmniejsza liczba kolorów, niezbędnych w Cocoloring o G . Wykresy o kochromatycznej liczbie 2 są dokładnie grafami dwudzielnymi , dopełnieniami grafów dwudzielnych i grafów podzielonych .
Warunek, że każda klasa koloru jest kliką lub jest niezależnym zbiorem jest słabszy niż warunek kolorowania (gdzie każda klasa koloru musi być niezależnym zbiorem) i silniejszy niż dla podkolorowania (in) ( gdzie każda klasa koloru musi być rozłączny związek klik); wynika, że liczba cochromatique z G jest mniejsza niż lub równa liczby chromatycznej z G , i jest większa niż lub równa liczbie podpotoków chromatycznej G .
Ko-kolorowanie zostało po raz pierwszy nazwane i zbadane przez Lesniaka i Straighta (1977) . Jørgensen (1995) charakteryzuje krytyczne grafy trójchromatyczne, podczas gdy Fomin, Kratsch i Novelli (2002) opisują algorytmy przybliżające liczbę kochromatyczną grafu. Zverovich (2000) definiuje klasę doskonałych grafów kochromatycznych , analogiczną do definicji doskonałych grafów poprzez kolorowanie grafów, i podaje zakazaną charakterystykę podgrafów tych grafów.