Skip to main content
1 of 5
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Here is a counterexample to Conjecture 1.

Claim. $\mathcal{C}(H) = \mathcal{C}(H)^{{\perp}{\perp}}$ for all induced subgraphs $H$ of $P_4$.

Proof. Since every induced subgraph of $P_4$ is a cograph, it suffices to prove the claim for $H=P_4$. Let $V(P_4)=\{1,2,3,4\}$ and $E(P_4)=\{12, 23, 34\}$. Clearly, $\mathcal{C}(P_4)=E(P_4)$. Thus, $\mathcal{C}(P_4)^{{\perp}}=\{13, 24\}$. Therefore, $\mathcal{C}(P_4)^{{\perp}{\perp}}=\{12,23,34\}=\mathcal{C}(P_4)$.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187