On the Complete Width and Edge Clique Cover Problems

Abstract

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}_i\subseteq V$, $1\le i\le k$, such that the graph $G'$ obtained from G by adding some new edges between certain vertices inside the sets $\mathtt {N}_i$, $1\le i\le k$, is a complete graph. The complete width problem is to compute the complete width of a given graph. In this paper we study the complete width problem. We show that the complete width problem is NP-hard 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 $K_{2,2,2}$-free co-bipartite graphs and polynomially solvable on $K_{2,2}$-free co-bipartite graphs and on $(2K_2, C_4)$-free graphs. We also determine all graphs of small complete width $k\le 3$.