  A graph is $k$-clique-extendible if there is an ordering of the vertices such
that whenever two $k$-sized overlapping cliques $A$ and $B$ have $k-1$ common
vertices, and these common vertices appear between the two vertices $a,b\in
(A\setminus B)\cup (B\setminus A)$ in the ordering, there is an edge between
$a$ and $b$, implying that $A\cup B$ is a $(k+1)$-sized clique. Such an
ordering is said to be a $k$-C-E ordering. These graphs arise in applications
related to modelling preference relations. Recently, it has been shown that a
maximum sized clique in such a graph can be found in $n^{O(k)}$ time when the
ordering is given. When $k$ is $2$, such graphs are precisely the well-known
class of comparability graphs and when $k$ is $3$ they are called
triangle-extendible graphs. It has been shown that triangle-extendible graphs
appear as induced subgraphs of visibility graphs of simple polygons, and the
complexity of recognizing them has been mentioned as an open problem in the
literature.
  While comparability graphs (i.e. $2$-C-E graphs) can be recognized in
polynomial time, we show that recognizing $k$-C-E graphs is NP-hard for any
fixed $k \geq 3$ and co-NP-hard when $k$ is part of the input. While our
NP-hardness reduction for $k \geq 4$ is from the betweenness problem, for
$k=3$, our reduction is an intricate one from the $3$-colouring problem. We
also show that the problems of determining whether a given ordering of the
vertices of a graph is a $k$-C-E ordering, and that of finding an $\ell$-sized
(or maximum sized) clique in a $k$-C-E graph, given a $k$-C-E ordering, are
complete for the parameterized complexity classes co-W[1] and W[1]
respectively, when parameterized by $k$. However we show that the former is
fixed-parameter tractable when parameterized by the treewidth of the graph.
