În teoria grafurilor , un Cocoloring unui grafic G este o atribuire de culori la nodurile astfel încât fiecare culoare forme de clasă un set independent în G sau graficul complement al G . Numărul cochromatique z ( G ) din G este cel mai mic număr de culori necesare într - o Cocoloring de G . Graficele numărului 2 cromatic sunt exact grafice bipartite , complementare ale graficelor bipartite și grafice divizate .
Condiția ca fiecare clasă de culoare să fie o clică sau să fie un set independent este mai slabă decât condiția de colorare (unde fiecare clasă de culoare trebuie să fie un set independent) și este mai puternică decât pentru sub-colorare (în) (unde fiecare clasă de culoare trebuie să fie o unire disjunctă de clici); rezultă că numărul de cochromatique G este mai mic sau egal cu numărul cromatic al G , și este mai mare sau egal cu numărul de sub - cromatice G .
Co-colorarea a fost numită și studiată pentru prima dată de Lesniak și Straight (1977) . Jørgensen (1995) caracterizează graficele tricromatice critice, în timp ce Fomin, Kratsch și Novelli (2002) descriu algoritmi pentru a aproxima numărul cromatic al unui grafic. Zverovich (2000) definește o clasă de grafice cocromatice perfecte , analogă definiției graficelor perfecte prin colorarea graficelor și oferă o caracterizare interzisă a subgrafului acestor grafice.