#### Preamble #1

There are two common equivalent definitions of cographs:

- the smallest class that includes $K_1$ and is closed under disjoint union and complementation (or join);
- the finite $P_4$-free graphs (i.e. no induced $P_4$ subgraphs).

An alternative, less common definition is:

- the finite graphs whose _every induced subgraph_ has the CK property.

Where a graph has the CK property iff every maximal clique intersects every maximal kernel (a.k.a. stable set, independent set, or anti-clique) at _exactly one vertex._

#### Preamble #2

Given a family of sets $\mathcal{X}$ define
$$
\mathcal{X}^\perp = \left\{ X \subseteq \bigcup\mathcal{X} \;\middle|\; \forall Y \in \mathcal{X}. |X \cap Y| = 1 \right\}
$$
i.e. $\mathcal{X}^\perp$ is the family of _all_ subsets of $\bigcup\mathcal{X}$ that intersect every set in $\mathcal{X}$ at _exactly one point._

Let $\mathcal{C}(G)$ denote the family of all _maximal cliques_ of the graph $G$:

**Proposition.** _If $G$ is a cograph, then $\mathcal{C}(G) = \mathcal{C}(G)^{{\perp}{\perp}}$._

#### The question

Is there any known proof or counterexample for the following conjecture?

**Conjecture 1.** _If $\mathcal{C}(H) = \mathcal{C}(H)^{{\perp}{\perp}}$ for all induced subgraphs $H$ of a finite graph $G$, then $G$ is a cograph._

#### My attempts

I attempted a proof, but I got stuck.

I would like to show that

> _For any finite $G$ such that $\mathcal{C}(G) = \mathcal{C}(G)^{{\perp}{\perp}}$, $\mathcal{C}(G)^\perp$ is the set of all maximal kernels of $G$._

The reverse inclusion here is just the CK property on $G$, and then the conjecture follows from the alternative definition of cograph.

_Incomplete proof._ The forward inclusion is easy. For the reverse one, observe that _any_ maximal kernel $k \in \mathcal{K}(G)$ intersects _each_ maximal clique at _one vertex at most._ Now I must use the fact that $\mathcal{C}(G) = \mathcal{C}(G)^{{\perp}{\perp}}$, but I can't see how. For example I would like to argue that $k$ can always be completed to form a member of $\mathcal{C}(G)^\perp$: then, because of the forward inclusion, that completion must be $k$ itself!

I have tried and failed to construct counterexamples. I can construct a lot of graphs with some maximal kernel that's not in $\mathcal{C}(G)^\perp$, but they do not satisfy the hypothesis either. I might be missing something obvious though.

The point where I got stuck seems to be crucial in many ways.
For example, I am also wondering whether

**Conjecture 2.** If $\mathcal{X} = \mathcal{X}^{{\perp}{\perp}}$ then $\mathcal{X} = \mathcal{C}(G_{\mathcal{X}})$.

Where $G_{\mathcal{X}}$ is the graph whose vertices are all elements of members of $\mathcal{X}$ (i.e. $V_{G_{\mathcal{X}}} = \bigcup\mathcal{X}$) and such that there is an edge on $u,v$ iff they appear together in some member of $\mathcal{X}$.

Similarly, one finds that the crucial step in the proof (where I got stuck again) involves being able to complete a set $X$ that intersects _some_ members of $\mathcal{X}^\perp$ at exactly one point to one that intersects _all_ members of $\mathcal{X}^\perp$ at exactly one point.

In other words, both conjectures would follow from

**Conjecture 3.** If $\mathcal{X} = \mathcal{X}^{{\perp}{\perp}}$ and $X \subseteq \bigcup\mathcal{X}$ intersects all members of $\mathcal{X}$ at _at most one point,_ then there is $Y \in \mathcal{X}^\perp$ such that $X \subseteq Y$.

(if necessary, it is ok to restrict conjectures 2,3 to the finite case)