2
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Nov 8, 2021 at 9:06
  • $\begingroup$ @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? $\endgroup$
    – Cyriac Antony
    Nov 8, 2021 at 9:10
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Nov 8, 2021 at 9:30
  • $\begingroup$ 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.) $\endgroup$
    – Emil Jeřábek
    Nov 8, 2021 at 10:10
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Emil Jeřábek
    Nov 8, 2021 at 10:20

1 Answer 1

Reset to default
3
$\begingroup$

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.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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