# Extending cographs with product operation

Let $$\mathcal{C}$$ be the class of undirected graphs defined inductively as follows:

• A single vertex is in $$\mathcal{C}$$;
• If $$G\in\mathcal{C}$$ then its complement $$\overline{G}$$ is in $$\mathcal{C}$$;
• If $$G,H\in\mathcal{C}$$ then their disjoint union $$G\oplus H$$ is in $$\mathcal{C}$$;
• If $$G,H\in\mathcal{C}$$ then their tensor product $$G\otimes H$$ is in $$\mathcal{C}$$.

This class of graphs appears in linear logic: this is how coherent spaces are defined.

I would like to now if this class have been studied from the point of view of graph theory. Does it have a name? Does it admit other characterizations?

If we restrict the definition to the first three lines we get cographs. But when we add the product operation we can create the 4-nodes path $$P_4$$, clique-width is then $$>2$$. But is the clique-width bounded for the whole class?

It was not clear for me how to generate paths of arbitrary lengths. This can be done by induction as follows, where the induction hypothesis is:

"$$\forall n$$, there is a graph $$G_n$$ of $$\mathcal{C}$$ containing $$P_n$$ as an induced subgraph"

• The paths $$P_2$$ and $$P_3$$ are clearly in $$\mathcal{C}$$. Take $$G_2$$ and $$G_3$$ to be respectively $$P_2$$ and $$P_3$$.

• For $$n\geq 4$$, we define $$G_n$$ as the tensor product of $$G_{n-1}$$ (obtained by IH) with the graph $$H_n$$ whose set of vertices is $$[1,n]$$ and which contains an edge between every pair of vertices except between $$n$$ and $$n-3$$. The graph $$H_n$$ is clearly a cograph thus belongs to $$\mathcal{C}$$. It is not very hard to see that $$G_{n-1}\otimes H_n$$ contains $$P_n$$ as an induced subgraph.

• Following your construction; i think for every graph G your class contains a graph H that contains G as an induced subgraph Nov 11, 2020 at 23:16
• That is right, interesting ! Nov 12, 2020 at 11:32

A path has cliquewidth $$3$$, but the tensor product of two paths of length $$n$$ will contain a $$\Omega(n) \times \Omega(n)$$ size grid as an induced subgraph. And $$n \times n$$ grids are known to have cliquewidth $$\Omega(n)$$ (see “The rank-width of the square grid“ by Vít Jelínek)
• It was not clear for me why $\mathcal{C}$ contains paths of arbitrary lengths. I updated my post to make this clear. Nov 10, 2020 at 9:48