• Let us consider a $(C,S,I)$-partition of a pseudo-split graph $G$. If $S$ is empty, then $G$ is a split graph and therefore it is polar. Otherwise, $S$ induces a 5-cycle $(v_0,v_1,v_2,v_3,v_4)$ and we have that $(C\cup\{v_0,v_2\}, I\cup\{v_1,v_3,v_4\})$ is a polar partition of G. Hence pseudo-split graphs are polar.
• It can easily be verified that the join of $K_1$ with a 5-cycle is not monopolar, but the disjoint union of a 5-cycle with an independent set is. Hence, if for a $(C,S,I)$-partition of a pseudo-split graph both $C$ and $S$ are non-emtpy, then $G$ is not monopolar. If $S$ is empty, then $G$ is split and therefore monopolar and if $C$ is empty, then $G$ is also monopolar, as stated. Thus $G$ is monopolar iff at least one of $C,S$ is empty, which can be decided from the degree sequence of $G$ in linear time.

• (0,3)-colorable $\subseteq$ probe (1,2)-colorable. Because we can turn one of the three stable sets of a tripartite graph into a clique to obtain a (1,2)-colorable graph.
• cochromatic number is bounded for probe (2,2)-colorable. Because probe (p,q)-colorable $\subseteq$ (p,q+1)-colorable in general, and (p,q+1)-colorable has cochromatic number at most p+q+1.
• cochromatic number is bounded for (p,q$\le$ 2)-colorable. They have cochromatic number at most p+2.
• cochromatic number is unbounded for cluster. $n K_n$ has cochromatic number n.
• cochromatic number is unbounded for girth $\ge 9$. By
  [1734]

  P. Erdos
  Graph theory and probability
  Canadian J. of Math. 11 34-38 (1959)
  
  (see also here), there exists graphs on $n$ vertices with girth $\ge 9$ and no stable set of size $n/k$ for every fixed $k$. Also, since they have no triangles, they have no cliques of size 3 or greater, so they have no cocoloring with a fixed number of colors.
• distance to cograph is unbounded for $(2K_2,C_4,C_5,claw,diamond)$-free. Let $G_t$ be graph obtained from $K_t$ by adding a pendant vertex to every vertex of $K_t$. So $G_2$ is $P_4$. Removing $r$ vertices from $G_t$ gives a graph containing an induced graph $G_{t-r}$
• line graphs of planar cubic bipartite graphs $\subseteq$ planar of maximum degree 4. From a planar embedding of a planar cubic bipartite graph, we connect the middles of incident edges to obtain a 4-regular planar line graph.

The proof goes by induction and makes use of the following claim: Every ptolemaic graph contains a leaf (vertex with only one neighbor), two proper twins, or two false twins that are simplicial.

As base case we have that $K_1$ obviously is both ptolemaic and admits an RDP model.

For the induction step, we assume that every ptolemaic graph with $n−1$ vertices admit RDP models, and look at an arbitrary ptolemaic graph $G$ with $n$ vertices. By the above claim, $G$ contains a vertex $v$ of one of the three types. Furthermore, according to the induction hypothesis, $G\setminus v$ is an RDP graph and admits an RDP model $(T, P)$. We look at the three types $v$ can have and show that in each case, we can augment the RDP model to include also $v$:

• $v$ is a leaf. In this case, $v$ has a single neighbor $u$. We look at the directed path $P_u$ corresponding to $u$ in the RDP model. Specifically, we look at the bottommost node $bu$ of $P_u$. Adding a child $c$ to $b_u$ and extending $P_u$ to this new node will not break the property of being an RDP model. Furthermore, we can add a new path $P_v$ corresponding to $v$, that only consists of the node $c$, and add it to $P$. This new model is clearly an RDP model of $G$.

• $v$ has a true twin $v′$. In this case, we simply make a new path $P_v = P_{v′}$ and add it to $P$. This must clearly be an RDP model of $G$.

• $v$ is simplicial and has a false twin $v′$. In this case, we look at the path $P_{v′}$. Since the neighborhood $S$ of $v$ and $v′$ is a clique, and directed paths have the Helly property, we know there is at least one node $s\in P_{v′}$ such that the cover $V(s)$ - i.e. the set of vertices whose paths contain $s$ - is equal to $S$. As such, we know that we can shrink the path $P_{v′}$ down to only include $s$. Subdividing the edge from the parent of $s$ to $s$, and extending every path in $S$ through the subdivision node $s′$, will not destroy the property of being an RDP model. Then, we can make a new path $P_v$ that only includes $s′$, and add it to $P$. The resulting RDP is clearly an RDP of $G$.

In every case, we see that there exists an RDP model of G. QED. (S. Høgemo). A proof is also attributed to

To check that a graph $G$ is $(C_{n+3} \cup K_1)$-free, we can simply try the following: for each vertex $v$, delete $v$ and its neighbourhood, and check that the resulting graph is $C_{n+3}$-free --- in other words, that it has no cycle at all, or equivalently that it is a forest, and this is easily done in O(V+E). Then $G$ is $(C_{n+3} \cup K_1)$-free iff for every vertex $v$, the graph obtained by removing $N[v]$ is a forest, so we should have something like O(V(V+E)) for the running time.

Diamonds and paws can be recognized in polynomial time using brute force. So we have a polynomial-time recognition algorithm for ($C_{n+3} \cup K_1$, diamond, paw)-free graphs.