Complexity of Graph covering Problems for Graphs of Low Degree

Abstract

We consider the following three problems: Given a graph $G$,

1. What is the smallest number of cliques into which the edges of $G$ can be partitioned?
2. How many cliques are needed to cover the edges of $G$?
3. Can the edges of $G$ be partitioned into maximal cliques of $G$?

All three problems are known to be NP-complete for general $G$. We show here that: (1) is NP-complete for $\mathrm{\Delta }(G)\ge 5$, but can be solved in polynomial time if $\mathrm{\Delta }(G)\le 4$ (the latter has already been proved by Pullman $[P]$); (2) is NP-complete for $\mathrm{\Delta }(G)\ge 6$, and polynomial for $\mathrm{\Delta }(G)\le 5$; (3) is NP-complete for $\mathrm{\Delta }(G)\ge 8$ and polynomial time for $\mathrm{\Delta }(G)\le 7$.