Skip to main content
Post Undeleted by Tony Huynh
deleted 71 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

I define theThe equivalence relation asthat HJRW defines themin the comments (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 onrelated to the cochromatic number $z(G)$ of a graph $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. Thus, the number of such equivalence classes gives an upper bound on the cochromatic number.

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.

The equivalence relation that HJRW defines in the comments (that is twin vertices may be adjacent) is related to the cochromatic number $z(G)$ of a graph $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. Thus, the number of such equivalence classes gives an upper bound on the cochromatic number.

Post Deleted by Tony Huynh
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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.