<p>As written, the problem is NP-complete even when you require the elements of <span class="math-container">$S$</span> to be pairwise disjoint (which also implies that every vertex belongs to a unique element of <span class="math-container">$S$</span>): as a reduction from <span class="math-container">$q$</span>-COLOURABILITY, we can attach to each vertex <span class="math-container">$q-1$</span> new vertices to form a <span class="math-container">$q$</span>-clique.</p>
<p>This does not contradict the results from the cited paper by Klotz, because in that paper, “clique cover” means “clique edge cover” rather than “clique vertex cover”.</p>
<p>If you restate the question with clique edge covers, i.e., requiring that each edge of <span class="math-container">$G$</span> is included in a <span class="math-container">$q$</span>-clique, the problem is still NP-complete: similar to the above, we can attach to each edge <span class="math-container">$q-2$</span> new vertices to form a <span class="math-container">$q$</span>-clique. This will make <span class="math-container">$|C\cap D|\le1$</span> for each distinct <span class="math-container">$C,D\in S$</span>. (It will violate condition (ii), as every original vertex belongs to as many elements of <span class="math-container">$S$</span> as was its degree in the original graph.)</p>

CC BY-SA 4.0
2021-11-08T13:27:46.230Z
2021-11-08T13:27:46.230Z
Emil Jeřábek
<p>Let <span class="math-container">$q\geq 3$</span>. We know that <span class="math-container">$q$</span>-COLORABILITY is an NP-complete problem.</p>
<p>Suppose that <span class="math-container">$G$</span> is a graph such that <strong>each vertex of <span class="math-container">$G$</span> is part of a <span class="math-container">$q$</span>-clique</strong> (i.e. <span class="math-container">$K_q$</span>). Since we may assume that <span class="math-container">$G$</span> does not contain <span class="math-container">$K_{q+1}$</span>, the condition is the same as saying that <span class="math-container">$G$</span> has a clique cover <span class="math-container">$S$</span> comprised of maximum cliques in <span class="math-container">$G$</span>.<br />
Does this condition make it easy to solve <span class="math-container">$q$</span>-COLORABILITY of <span class="math-container">$G$</span>? If not, would the following extra condition make it possible:
<span class="math-container">$|C\cap D|\leq 2$</span> for every two distinct members <span class="math-container">$C,D\in S$</span> ?</p>
<p><em>Remark</em>: there are known results on <span class="math-container">$q$</span>-COLORABILITY when <span class="math-container">$G$</span> has a clique <strong>edge</strong> cover <span class="math-container">$S$</span> such that (i) <span class="math-container">$|C\cap D|\leq 1$</span> for every two distinct members <span class="math-container">$C,D\in S$</span>, and (ii) each vertex of <span class="math-container">$G$</span> belong to at most 2 members in <span class="math-container">$S$</span>. For instance, see Walter Klotz, Clique Covers and Coloring Problems of Graphs.</p>

CC BY-SA 4.0
2021-11-08T09:06:29.207Z
This is NP-complete even if you ask distinct elements of $S$ to be *disjoint*: just attach to each original vertex $q-1$ new vertices that together form a $q$-clique.
Emil Jeřábek
CC BY-SA 4.0
2021-11-08T09:10:35.047Z
@EmilJeřábek, Ah. sure. You are right. Are clique covers comprised of max cliques advantageous over usual clique covers if we are ready to impose both restrictions of type (i) and type (ii) in the remark?
Cyriac Antony
CC BY-SA 4.0
2021-11-08T09:30:44.150Z
The construction in my comment *does* satisfy both (i) and (ii): since the cliques in $S$ are disjoint, $|C\cap D|=0\le1$ for distinct $C,D\in S$, and each vertex belongs to $1\le2$ elements of $S$. I don’t know what’s in the paper you cite, but perhaps you are missing or misreading some of the conditions.
Emil Jeřábek
CC BY-SA 4.0
2021-11-08T10:10:57.240Z
Ok, I looked up the paper. It’s clear from e.g. the proof of Lemma 2.1 that for Klotz, “clique cover” actually means “clique *edge* cover”. (It's amazing how he managed to make the definition on the first page completely ambiguous: “$G=\bigcup_{j=1}^mC_j$” can mean anything, depending on whether the $G$ and $C_j$ notations are interpreted as sets of vertices or sets of edges.)
Emil Jeřábek
CC BY-SA 4.0
2021-11-08T10:20:07.270Z
Note that if you strengthen your original conditions to a clique edge cover (i.e., every edge belongs to a $q$-clique), then $q$-COLORABILITY is still NP-complete: attach to each original edge $q-2$ vertices to make it a $q$-clique. This will satisfy $|C\cap D|\le1$ for distinct $C,D\in S$. (Each vertex will belong to as many cliques from $S$ as was its degree in the original graph.)
Emil Jeřábek
CC BY-SA 4.0
2021-11-08T10:32:29.333Z
Thank you. The comments completely answer the question. If  it is converted into an answer, I shall accept it. If the question is not research-level, i shall vote to close the question.
Cyriac Antony
CC BY-SA 4.0
2021-11-09T13:35:06.593Z
almost all degree 5 graphs are 3 colorable. almost all degree 9 graphs are 4 colorable. almost all degree 16 graphs are thought to be 5 colorable. daniel +GREs 2380
daniel pehoushek
CC BY-SA 4.0
2021-11-13T21:53:03.473Z
More generally, [perfect graphs](https://en.wikipedia.org/wiki/Perfect_graph#Algorithms_on_perfect_graphs) are one class of graphs for which COLORABILITY is famously solvable in polynomial time... The condition for being a perfect graph has at least some superficial similarity to what you propose.
Neal Young
<graph-theory><graph-colouring>
Does abundance of max cliques make it easy to solve COLORABILITY?
Cyriac Antony
# Does abundance of max cliques make it easy to solve COLORABILITY?

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

Let $q\geq 3$. We know that $q$-COLORABILITY is an NP-complete problem.

Suppose that $G$ is a graph such that **each vertex of $G$ is part of a $q$-clique** (i.e. $K\_q$). Since we may assume that $G$ does not contain $K\_{q+1}$, the condition is the same as saying that $G$ has a clique cover $S$ comprised of maximum cliques in $G$.  
Does this condition make it easy to solve $q$-COLORABILITY of $G$? If not, would the following extra condition make it possible:
$|C\cap D|\leq 2$ for every two distinct members $C,D\in S$ ?

*Remark*: there are known results on $q$-COLORABILITY when $G$ has a clique **edge** cover $S$ such that (i) $|C\cap D|\leq 1$ for every two distinct members $C,D\in S$, and (ii) each vertex of $G$ belong to at most 2 members in $S$. For instance, see Walter Klotz, Clique Covers and Coloring Problems of Graphs.

**Tags:** graph-theory, graph-colouring
> **Comments:**
> **username_1**: This is NP-complete even if you ask distinct elements of $S$ to be *disjoint*: just attach to each original vertex $q-1$ new vertices that together form a $q$-clique.  
> **username_0**: @EmilJeřábek, Ah. sure. You are right. Are clique covers comprised of max cliques advantageous over usual clique covers if we are ready to impose both restrictions of type (i) and type (ii) in the remark?  
> **username_1**: The construction in my comment *does* satisfy both (i) and (ii): since the cliques in $S$ are disjoint, $|C\cap D|=0\le1$ for distinct $C,D\in S$, and each vertex belongs to $1\le2$ elements of $S$. I don’t know what’s in the paper you cite, but perhaps you are missing or misreading some of the conditions.  
> **username_1**: Ok, I looked up the paper. It’s clear from e.g. the proof of Lemma 2.1 that for Klotz, “clique cover” actually means “clique *edge* cover”. (It's amazing how he managed to make the definition on the first page completely ambiguous: “$G=\bigcup_{j=1}^mC_j$” can mean anything, depending on whether the $G$ and $C_j$ notations are interpreted as sets of vertices or sets of edges.)  
> **username_1**: Note that if you strengthen your original conditions to a clique edge cover (i.e., every edge belongs to a $q$-clique), then $q$-COLORABILITY is still NP-complete: attach to each original edge $q-2$ vertices to make it a $q$-clique. This will satisfy $|C\cap D|\le1$ for distinct $C,D\in S$. (Each vertex will belong to as many cliques from $S$ as was its degree in the original graph.)  
> **username_0**: Thank you. The comments completely answer the question. If  it is converted into an answer, I shall accept it. If the question is not research-level, i shall vote to close the question.  
> **username_2**: almost all degree 5 graphs are 3 colorable. almost all degree 9 graphs are 4 colorable. almost all degree 16 graphs are thought to be 5 colorable. daniel +GREs 2380  
> **username_3**: More generally, [perfect graphs](https://en.wikipedia.org/wiki/Perfect_graph#Algorithms_on_perfect_graphs) are one class of graphs for which COLORABILITY is famously solvable in polynomial time... The condition for being a perfect graph has at least some superficial similarity to what you propose.  

---

## 1 answers

### Answer by username_1 on 2021-11-08. Score: 3 | Accepted answer

As written, the problem is NP-complete even when you require the elements of $S$ to be pairwise disjoint (which also implies that every vertex belongs to a unique element of $S$): as a reduction from $q$-COLOURABILITY, we can attach to each vertex $q-1$ new vertices to form a $q$-clique.

This does not contradict the results from the cited paper by Klotz, because in that paper, “clique cover” means “clique edge cover” rather than “clique vertex cover”.

If you restate the question with clique edge covers, i.e., requiring that each edge of $G$ is included in a $q$-clique, the problem is still NP-complete: similar to the above, we can attach to each edge $q-2$ new vertices to form a $q$-clique. This will make $|C\cap D|\le1$ for each distinct $C,D\in S$. (It will violate condition (ii), as every original vertex belongs to as many elements of $S$ as was its degree in the original graph.)


---

