<p>Let <span class="math-container">$G=(V,E)$</span> be an arbitrary instance of <span class="math-container">$3$</span>-coloring.
Construct a new graph <span class="math-container">$G'=(V',E')$</span> as follows:</p>
<ul>
<li><span class="math-container">$V'$</span> contains all the vertices in <span class="math-container">$V$</span>, and for every edge <span class="math-container">$e\in E$</span> it contains a corresponding new vertex <span class="math-container">$x(e)$</span>.</li>
<li><span class="math-container">$E'$</span> contains all the edges in <span class="math-container">$E$</span>, and for every edge <span class="math-container">$e=\{u,v\}\in E$</span> it contains the two new edges <span class="math-container">$\{x(e),u\}$</span> and <span class="math-container">$\{x(e),v\}$</span>.</li>
</ul>
<p>Note the following:</p>
<ul>
<li>The sets <span class="math-container">$\{x(e),u,v\}$</span> form a <span class="math-container">$3$</span>-edge cover for <span class="math-container">$G'$</span>.</li>
<li>Graph <span class="math-container">$G$</span> is <span class="math-container">$3$</span>-colorable if and only if graph <span class="math-container">$G'$</span> is <span class="math-container">$3$</span>-colorable.</li>
</ul>
<p>Hence the answer to your first question (&quot;Suppose that we are given a <span class="math-container">$q$</span>-edge cover of <span class="math-container">$G$</span>. Does that make it easy to test whether <span class="math-container">$G$</span> has a <span class="math-container">$q$</span>-colouring?&quot;) should be negative.</p>

CC BY-SA 4.0
2021-08-01T11:23:22.967Z
2021-08-01T11:23:22.967Z
Gamow
<p>A <span class="math-container">$q$</span>-clique of a graph is a complete subgraph on <span class="math-container">$q$</span> vertices.
A <em><span class="math-container">$q$</span>-clique edge cover</em> of <span class="math-container">$G$</span> is a set of subgraphs of <span class="math-container">$G$</span> such that each subgraph is a <span class="math-container">$q$</span>-clique and each edge of G is contained in at least one of these subgraphs.
See <a href="https://en.wikipedia.org/wiki/Intersection_number_(graph_theory)#Clique_edge_covers" rel="nofollow noreferrer">[1]</a>, <a href="https://epubs.siam.org/doi/pdf/10.1137/1.9781611973105.75" rel="nofollow noreferrer">[2]</a> and <a href="https://doi.org/10.1002/jgt.22431" rel="nofollow noreferrer">[3]</a> for related topics.</p>
<p>We know that it is NP-hard to test whether <span class="math-container">$G$</span> has a <span class="math-container">$q$</span>-colouring.
Suppose that <span class="math-container">$G$</span> has a <span class="math-container">$q$</span>-edge cover (i.e., every edge of <span class="math-container">$G$</span> is part of a <span class="math-container">$q$</span>-clique in <span class="math-container">$G$</span>) and we give a <span class="math-container">$q$</span>-edge cover of <span class="math-container">$G$</span>.<br />
Does that make it easy to test whether <span class="math-container">$G$</span> has a <span class="math-container">$q$</span>-colouring? I suppose the answer is 'no' for general graphs.<br />
<strong>Are there graph classes <span class="math-container">$\mathscr{G}$</span> such that the answer will be 'yes' for graps <span class="math-container">$G\in\mathscr{G}$</span> ?</strong></p>

<cc.complexity-theory><graph-theory><time-complexity><graph-colouring>
Graph classes where giving a q-clique edge cover makes testing for q-colouring easy
Cyriac Antony
# Graph classes where giving a q-clique edge cover makes testing for q-colouring easy

(Asked by: username_0 on 2021-08-01)

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]](https://en.wikipedia.org/wiki/Intersection_number_(graph_theory)#Clique_edge_covers), [[2]](https://epubs.siam.org/doi/pdf/10.1137/1.9781611973105.75) and [[3]](https://doi.org/10.1002/jgt.22431) 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}$ ?**

**Tags:** cc.complexity-theory, graph-theory, time-complexity, graph-colouring

---

## 1 answers

### Answer by username_1 on 2021-08-01. Score: 4

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.


---

