Complexity of Graph covering Problems for Graphs of Low Degree

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 \(\Delta(G) \geq 5\), but can be solved in polynomial time if \(\Delta(G) \leq 4\) (the latter has already been proved by Pullman \([P]\)); (2) is NP-complete for \(\Delta(G) \geq 6\), and polynomial for \(\Delta(G) \leq 5\); (3) is NP-complete for \(\Delta(G) \geq 8\) and polynomial time for \(\Delta(G) \leq 7\).