1
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.