Let $G=(V,E)$ be a simple, undirected graph. A clique cover is a set ${\cal C}\subseteq {\cal P}(V)$ such that

  1. every element of ${\cal C}$ is a clique, and
  2. $\bigcup {\cal C} = V$.

We call a clique cover ${\cal C}$ beatable if there is a clique cover ${\cal C}_1$ such that $$|{\cal C}_1 - {\cal C}| < |{\cal C} - {\cal C}_1|.$$ Non-beatable clique covers are called unbeatable.

It is easy to prove that every finite graph has an unbeatable clique cover. But what about infinite graphs?

  • $\begingroup$ what is $\mathcal{C-C_1}$ and $\mathcal{C_1-C}$ here? $\endgroup$ – user94040 Dec 14 '16 at 8:59
  • 1
    $\begingroup$ @AJ. He means the set difference. So, the condition states that in going from $\cal C$ to $\cal C_1$, you've removed more cliques than you've added. $\endgroup$ – Joel David Hamkins Dec 14 '16 at 13:30

I think it is a known conjecture. The special case that there always exists a clique cover such that the union of any two of those cliques is not a clique, can be proved from Zorn's lemma (or without it), cf. my book with Totik: Problems and Theorems in Classical Set Theory, Problem 14.6.(m). This special case is actually equivalent to the axiom of choice: F. Galvin, P. Komjáth: Graph colorings and the axiom of choice, Periodica Math. Hung. 22 (1991), 71–75.

| cite | improve this answer | |

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.