8
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ what is $\mathcal{C-C_1}$ and $\mathcal{C_1-C}$ here? $\endgroup$
    – user94040
    Commented Dec 14, 2016 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
    Commented Dec 14, 2016 at 13:30

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .