On the Triangle Clique Cover and $K_t$ Clique Cover Problems

An edge clique cover of a graph is a set of cliques that covers all edges of the graph. We generalize this concept to “$K_t$ clique cover”, i.e. a set of cliques that covers all complete subgraphs on $t$ vertices of the graph, for every $t\ge 1$. In particular, we extend a classical result of Erd"os, Goodman, and P'osa (1966) on the edge clique cover number ($t=2$), also known as the intersection number, to the case $t=3$. The upper bound is tight, with equality holding only for the Tur'an graph $T(n,3)$. We also extend an algorithm of Scheinerman and Trenk (1999) to solve a weighted version of the $K_t$ clique cover problem on a superclass of chordal graphs. We also prove that the $K_t$ clique cover problem is NP-hard.