Skip to main content
5 of 5
deleted 201 characters in body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Here is a proof of Conjecture 1.

Proof. We prove the contrapositive. Suppose that $G$ is not a cograph. Then $G$ has an induced subgraph $H$ such that $H \simeq P_4$. Let $V(H)=\{1,2,3,4\}$ and $E(H)=\{12,23,34\}$. Thus, $\mathcal{C}(H)=E(H)$ and so $\mathcal{C}(H)^{\perp}=\{13,24\}$. It follows that $\mathcal{C}(H)^{{\perp}{\perp}}=\{12,23,34,14\} \neq \mathcal{C}(H)$.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187