<p>A path has cliquewidth <span class="math-container">$3$</span>, but the tensor product of two paths of length <span class="math-container">$n$</span> will contain a <span class="math-container">$\Omega(n) \times \Omega(n)$</span> size grid as an induced subgraph. And <span class="math-container">$n \times n$</span> grids are known to have cliquewidth <span class="math-container">$\Omega(n)$</span> (see “<em>The rank-width of the square grid</em>“ by Vít Jelínek)</p>

CC BY-SA 4.0
2020-11-10T09:14:59.200Z
Thank you for your answer !
A. D.
CC BY-SA 4.0
2020-11-10T09:48:14.180Z
It was not clear for me why $\mathcal{C}$ contains paths of arbitrary lengths. I updated my post to make this clear.
A. D.
CC BY-SA 4.0
2020-11-11T07:19:52.730Z
Yes, you are correct that just having cliquewidth 3 does not imply a construction using your operations, thanks for the catch and save :)
daniello
CC BY-SA 4.0
2020-11-09T21:00:44.103Z
2020-11-09T21:00:44.103Z
daniello
<p>Let <span class="math-container">$\mathcal{C}$</span> be the class of undirected graphs defined inductively as follows:</p>
<ul>
<li>A single vertex is in <span class="math-container">$\mathcal{C}$</span>;</li>
<li>If <span class="math-container">$G\in\mathcal{C}$</span> then its <a href="https://en.wikipedia.org/wiki/Complement_graph" rel="nofollow noreferrer">complement</a> <span class="math-container">$\overline{G}$</span> is in <span class="math-container">$\mathcal{C}$</span>;</li>
<li>If <span class="math-container">$G,H\in\mathcal{C}$</span> then their disjoint union <span class="math-container">$G\oplus H$</span> is in <span class="math-container">$\mathcal{C}$</span>;</li>
<li>If <span class="math-container">$G,H\in\mathcal{C}$</span> then their <a href="https://en.wikipedia.org/wiki/Tensor_product_of_graphs" rel="nofollow noreferrer">tensor product</a> <span class="math-container">$G\otimes H$</span> is in <span class="math-container">$\mathcal{C}$</span>.</li>
</ul>
<p>This class of graphs appears in linear logic: this is how coherent spaces are defined.</p>
<p>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?</p>
<p>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 <span class="math-container">$P_4$</span>, clique-width is then <span class="math-container">$&gt;2$</span>. But is the clique-width bounded for the whole class?</p>
<p>Thank you in advance for your help.</p>
<p><strong>Update after daniello's answer</strong></p>
<p>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:</p>
<p>&quot;<span class="math-container">$\forall n$</span>, there is a graph <span class="math-container">$G_n$</span> of <span class="math-container">$\mathcal{C}$</span> containing <span class="math-container">$P_n$</span> as an induced subgraph&quot;</p>
<ul>
<li><p>The paths <span class="math-container">$P_2$</span> and <span class="math-container">$P_3$</span> are clearly in <span class="math-container">$\mathcal{C}$</span>. Take <span class="math-container">$G_2$</span> and <span class="math-container">$G_3$</span> to be respectively <span class="math-container">$P_2$</span> and <span class="math-container">$P_3$</span>.</p>
</li>
<li><p>For <span class="math-container">$n\geq 4$</span>, we define <span class="math-container">$G_n$</span> as the tensor product of <span class="math-container">$G_{n-1}$</span> (obtained by IH) with the graph <span class="math-container">$H_n$</span> whose set of vertices is <span class="math-container">$[1,n]$</span> and which contains an edge between every pair of vertices except between <span class="math-container">$n$</span> and <span class="math-container">$n-3$</span>. The graph <span class="math-container">$H_n$</span> is clearly a cograph thus belongs to <span class="math-container">$\mathcal{C}$</span>. It is not very hard to see that <span class="math-container">$G_{n-1}\otimes H_n$</span> contains <span class="math-container">$P_n$</span> as an induced subgraph.</p>
</li>
</ul>

CC BY-SA 4.0
2020-11-11T23:16:41.663Z
Following your construction; i think for every graph G your class contains a graph H that contains G as an induced subgraph
daniello
CC BY-SA 4.0
2020-11-12T11:32:15.933Z
That is right, interesting !
A. D.
<reference-request><graph-theory><graph-classes><cliquewidth>
Extending cographs with product operation
A. D.
# Extending cographs with product operation

(Asked by: username_0 on 2020-11-09)

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](https://en.wikipedia.org/wiki/Complement_graph) $\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](https://en.wikipedia.org/wiki/Tensor_product_of_graphs) $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 username_1'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.

**Tags:** reference-request, graph-theory, graph-classes, cliquewidth

> **Comments:**
> **username_1**: Following your construction; i think for every graph G your class contains a graph H that contains G as an induced subgraph  
> **username_0**: That is right, interesting !  

---

## 1 answers

### Answer by username_1 on 2020-11-09. Score: 5

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)

> **Comments:**
> **username_0**: Thank you for your answer !  
> **username_0**: It was not clear for me why $\mathcal{C}$ contains paths of arbitrary lengths. I updated my post to make this clear.  
> **username_1**: Yes, you are correct that just having cliquewidth 3 does not imply a construction using your operations, thanks for the catch and save :)  

---

