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

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}$$ ?

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\}$$.
• 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.