Chapter XIII Clique Cover

Cliques as colors

Cliques in G are independent sets in G's complement. So clique cover is coloring, in disguise.

A clique cover partitions the vertex set into cliques:

V = C_{1} \cup C_{2} \cup \dots \cup C_{k}, each C_{i} a clique in G . (1)

The minimum k for which (1) holds is the clique cover number, written θ(G).

Karp's reduction is the cleanest of the 21. A clique in G is an independent set in the complement; so a clique cover of G is a coloring of the complement, giving the identity

θ (G) = χ (\overline{G}) . (2)

By (2), any algorithm for chromatic number solves clique cover on the complement. The decision problem (is θ(G) ≤ k?) is NP-complete for every fixed k from 3 upward.

Notable: on perfect graphs (Berge 1961, Lovász 1972), both clique cover and chromatic number are polynomial — a window of tractability inside the otherwise intractable family.

Figures, in plain terms

(1)

Same shape as chromatic number's set-partition (figure 1 of the previous chapter), with one swap.

V = C₁ ∪ C₂ ∪ ... ∪ C_k unions k disjoint vertex-groups to cover all of V — same as before.

But now the condition on each group is C_i a clique in G: every two vertices inside one group must be connected by an edge. (Compare chapter 12, where each group was an independent set — no edges inside.)

So "color groups must be edge-free" flipped to "color groups must be edge-complete." Independent sets and cliques are duals.

(2)

θ(G) is the clique cover number. The Greek letter is "theta."

χ(G) on the right is chromatic number from the previous chapter.

The bar over G — written complement of G — is the complement graph: same vertices, but every non-edge of G becomes an edge, and every edge becomes a non-edge.

The identity θ(G) = χ(complement of G) is the cleanest reduction in the 21. A clique in G is exactly an independent set in the complement; covering G with cliques is exactly coloring the complement. Same problem, swapped lens.