  Tree-width has been proven to be a useful parameter to design fast and
efficient algorithms for intractable problems. However, while tree-width is low
on relatively sparse graphs can be arbitrary high on dense graphs. Therefore,
we introduce tree-clique width, denoted by $tcl(G)$ for a graph $G$, a new
width measure for tree decompositions. The main aim of such a parameter is to
extend the algorithmic gains of tree-width on more structured and dense graphs.
In this paper, we show that tree-clique width is NP-complete and that there is
no constant-factor approximation algorithm for any constant value $c$. We also
provide algorithms to compute tree-clique width for general graphs and for
special graphs such as cographs and permutation graphs. We seek to understand
further tree-clique width and its properties and to research whether it can be
used as an alternative where tree-width fails.
