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?

Thank you in advance for your help.

Update after daniello's answer

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.

  • 1
    $\begingroup$ Following your construction; i think for every graph G your class contains a graph H that contains G as an induced subgraph $\endgroup$ – daniello Nov 11 '20 at 23:16
  • $\begingroup$ That is right, interesting ! $\endgroup$ – A. D. Nov 12 '20 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)

  • $\begingroup$ Thank you for your answer ! $\endgroup$ – A. D. Nov 10 '20 at 9:14
  • 1
    $\begingroup$ It was not clear for me why $\mathcal{C}$ contains paths of arbitrary lengths. I updated my post to make this clear. $\endgroup$ – A. D. Nov 10 '20 at 9:48
  • 1
    $\begingroup$ Yes, you are correct that just having cliquewidth 3 does not imply a construction using your operations, thanks for the catch and save :) $\endgroup$ – daniello Nov 11 '20 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.