On the complete width and edge clique cover problems

A complete graph is the graph in which every two vertices are adjacent. For a graph (G=(V,E)), the complete width of G is the minimum k such that there exist k independent sets (mathtt {N}_isubseteq V), (1le ile k), such that the graph (G') obtained from G by adding some new edges between certain vertices inside the sets (mathtt {N}_i), (1le ile k), is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on (3K_2)-free bipartite graphs and polynomially solvable on (2K_2)-free bipartite graphs and on ((2K_2,C_4))-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on (overline{3K_2})-free co-bipartite graphs and polynomially solvable on (C_4)-free co-bipartite graphs and on ((2K_2, C_4))-free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most (2^k) vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most (2^k) vertices. Finally we determine all graphs of small complete width (kle 3).