Return to Revisions

I define the equivalence relation as HJRW defines them (that is twin vertices may be adjacent). In this way, each equivalence class is either a clique or a stable set (this is what you mention in the comments too). Thus, the number of such equivalence classes gives an upper bound on the cochromatic number $z(G)$ of $G$. The cochromatic number of $G$ is the minimum number of colours needed to colour $V(G)$ such that each colour class induces a clique or stable set.