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≥1. In particular, we extend a classical result of Erdös et al. (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án graph T(n,3). As part of the proof, we obtain new upper bounds on the classical intersection number, which may be of independent interest. 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.