<p>The clique width of graph $G$ is defined as minimum number of labels required to construct $G$ by using <a href="http://en.wikipedia.org/wiki/Clique-width" rel="nofollow">four operations</a>. 
I would like to know why the name clique width is given to this definition. How it is related to clique definition.  </p>

CC BY-SA 3.0
2014-11-24T10:13:42.577Z
It's reasonable to name it clique-width as clique-width of clique is bounded, unlike other width parameters.
Saeed
CC BY-SA 3.0
2014-11-24T12:46:33.643Z
The name may not be the best choice; some name had to be chosen though. There is a small commentary about this in [Algorithmic uses of the Feferman–Vaught Theorem](http://dx.doi.org/10.1016/j.apal.2003.11.002) by Makowsky. The name does seem better than $k$-NLC-graphs, though ;)
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-11-24T16:26:32.143Z
I think the idea of the name cliquewidth is that it essentially extends tree-width to a "tree of cliques".
daniello
<graph-theory><graph-algorithms>
Definition of Clique width of graph
Kumar
# Definition of Clique width of graph

(Asked by: username_0 on 2014-11-24)

The clique width of graph $G$ is defined as minimum number of labels required to construct $G$ by using [four operations](http://en.wikipedia.org/wiki/Clique-width).
I would like to know why the name clique width is given to this definition. How it is related to clique definition.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: It's reasonable to name it clique-width as clique-width of clique is bounded, unlike other width parameters.  
> **username_2**: The name may not be the best choice; some name had to be chosen though. There is a small commentary about this in [Algorithmic uses of the Feferman–Vaught Theorem](http://dx.doi.org/10.1016/j.apal.2003.11.002) by Makowsky. The name does seem better than $k$-NLC-graphs, though ;)  
> **username_3**: I think the idea of the name cliquewidth is that it essentially extends tree-width to a "tree of cliques".  

---

## 0 answers

