V teorii grafů , je Cocoloring grafu G je přiřazení barev , aby tak, že každá barva třídy svírá vrcholů nezávislý soubor v G nebo komplement grafu z G . Číslo cochromatique z ( G ) z G je nejmenší počet barev potřebných v Cocoloring z G . Grafy kochromatického čísla 2 jsou přesně bipartitní grafy , doplňky bipartitních grafů a dělené grafy .
Podmínka, že každá barevná třída je klika nebo je nezávislou sadou, je slabší než podmínka zbarvení (kde každá barevná třída musí být nezávislou sadou) a je silnější než pro podbarvení (in) (kde musí být každá barevná třída disjunktní spojení klik); z toho vyplývá, že cochromatique počet G je menší než nebo roven barevnosti z G , a je větší než nebo roven počtu sub-chromatický G .
Společné zbarvení poprvé pojmenovali a studovali Lesniak a Straight (1977) . Jørgensen (1995) charakterizuje kritické trichromatické grafy, zatímco Fomin, Kratsch a Novelli (2002) popisují algoritmy pro aproximaci kochromatického čísla grafu. Zverovich (2000) definuje třídu dokonalých kochromatických grafů , analogicky k definici dokonalých grafů pomocí zbarvení grafu, a poskytuje zakázanou subgrafickou charakteristiku těchto grafů.