Return to Answer

Here is a proof of Conjecture 1.

Proof. We proceed by induction on $|V(G)|$. We may clearly assume $|V(G)| \geq 4$. Since $\mathcal{C}(H) = \mathcal{C}(H)^{{\perp}{\perp}}$, for all induced subgraphs $H$ of $G$, we may assume (by induction) that every proper induced subgraph of $G$ is a cograph. Thus, $G$ is itself a cograph unless $G=P_4$. Let $V(G)=\{1,2,3,4\}$ and $E(G)=\{12,23,34\}$. Thus, $\mathcal{C}(G)=E(G)$ and so $\mathcal{C}(G)^{\perp}=\{13,24\}$. It follows that $\mathcal{C}(G)^{{\perp}{\perp}}=\{12,23,34,14\} \neq \mathcal{C}(G)$, which is a contradiction.

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)$.

Here is a proof of Conjecture 1.

Proof. It suffices to show that if $\mathcal{C}(H) = \mathcal{C}(H)^{{\perp}{\perp}}$, then $H$ has the CK property. First observe that every $S \in \mathcal{C}(H)^\perp$ is a stable set of $H$, otherwise $S$ would intersect some $K \in \mathcal{C}(H)$ in at least two vertices. Now, since $\mathcal{C}(H)^{{\perp}{\perp}}=\mathcal{C}(H)$ it follows that every maximal clique intersects every member of $\mathcal{C}(H)^\perp$ exactly once. Since each member of $\mathcal{C}(H)^\perp$ is contained in a maximal stable set, it follows that every maximal clique intersects every maximal stable set. Thus, $H$ has the CK property.

Here is a proof of Conjecture 1.

Proof. We proceed by induction on $|V(G)|$. We may clearly assume $|V(G)| \geq 4$. Since $\mathcal{C}(H) = \mathcal{C}(H)^{{\perp}{\perp}}$, for all induced subgraphs $H$ of $G$, we may assume (by induction) that every proper induced subgraph of $G$ is a cograph. Thus, $G$ is itself a cograph unless $G=P_4$. Let $V(G)=\{1,2,3,4\}$ and $E(G)=\{12,23,34\}$. Thus, $\mathcal{C}(G)=E(G)$ and so $\mathcal{C}(G)^{\perp}=\{13,24\}$. It follows that $\mathcal{C}(G)^{{\perp}{\perp}}=\{12,23,34,14\} \neq \mathcal{C}(G)$, which is a contradiction.

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 proper 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)$.

Here is a proof of Conjecture 1.

Proof. It suffices to show that if $\mathcal{C}(H) = \mathcal{C}(H)^{{\perp}{\perp}}$, then $H$ has the CK property. First observe that every $S \in \mathcal{C}(H)^\perp$ is a stable set of $H$, otherwise $S$ would intersect some $K \in \mathcal{C}(H)$ in at least two vertices. Now, since $\mathcal{C}(H)^{{\perp}{\perp}}=\mathcal{C}(H)$ it follows that every maximal clique intersects every member of $\mathcal{C}(H)^\perp$ exactly once. Since each member of $\mathcal{C}(H)^\perp$ is contained in a maximal stable set, it follows that every maximal clique intersects every maximal stable set. Thus, $H$ has the CK property.