Graph classes where giving a q-clique edge cover makes testing for q-colouring easy

Question

A $q$-clique of a graph is a complete subgraph on $q$ vertices. A $q$-clique edge cover of $G$ is a set of subgraphs of $G$ such that each subgraph is a $q$-clique and each edge of G is contained in at least one of these subgraphs. See [1], [2] and [3] for related topics.

We know that it is NP-hard to test whether $G$ has a $q$-colouring. Suppose that $G$ has a $q$-edge cover (i.e., every edge of $G$ is part of a $q$-clique in $G$) and we give a $q$-edge cover of $G$.
Does that make it easy to test whether $G$ has a $q$-colouring? I suppose the answer is 'no' for general graphs.
Are there graph classes $\mathscr{G}$ such that the answer will be 'yes' for graps $G\in\mathscr{G}$ ?

Answer 1

Let $G=(V,E)$ be an arbitrary instance of $3$-coloring. Construct a new graph $G'=(V',E')$ as follows:

• $V'$ contains all the vertices in $V$, and for every edge $e\in E$ it contains a corresponding new vertex $x(e)$.
• $E'$ contains all the edges in $E$, and for every edge $e=\{u,v\}\in E$ it contains the two new edges $\{x(e),u\}$ and $\{x(e),v\}$.

Note the following:

• The sets $\{x(e),u,v\}$ form a $3$-edge cover for $G'$.
• Graph $G$ is $3$-colorable if and only if graph $G'$ is $3$-colorable.

Hence the answer to your first question ("Suppose that we are given a $q$-edge cover of $G$. Does that make it easy to test whether $G$ has a $q$-colouring?") should be negative.