If $G=(V,E)$ is any nonempty, simple, undirected graph (finite or infinite), it can be covered with cliques in many ways, the least interesting being a cover by singletons. However, there is one clique cover that I am not sure exists at all in infinite graphs. But first, let's get the "terms and conditions" right.

Let us call a collection ${\cal M}$ of non-empty subsets of $V$ a clique cover if $\bigcup {\cal M} = V$ and every member of ${\cal M}$ is a clique (when regarded as an induced subgraph of $G$). We call it special if for any clique cover ${\cal J}$ of $G$ we have $|{\cal M}\setminus {\cal J}| \le |{\cal J}\setminus {\cal M}|$.

Question. Does any nonempty graph have a special clique cover? (The answer is yes for finite graphs.)

  • $\begingroup$ Small terminological comment: it would be shorter, and type-wise clearer, to replace "is a clique (when regarded as an induced subgraph of $G$)" with "induces a clique of $G$". $\endgroup$ – Peter Heinig Aug 1 '17 at 20:29
  • $\begingroup$ By the way, a clique cover of $G$ is nothing more than a proper vertex colouring of its complement. So it can also be phased as a vertex colouring problem. $\endgroup$ – Jon Noel Aug 1 '17 at 21:16
  • $\begingroup$ @JonNoel That's nice - do you know a solution of this vertex colouring problem? $\endgroup$ – Dominic van der Zypen Aug 2 '17 at 8:37

Your Answer

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

Browse other questions tagged or ask your own question.