Chapter 10 - Coverings

Summary

Some examples of covering problems

Many problems in graph theory can be formulated as an instance of the following, somewhat general, covering problem:

We are given two sets X and Y, and with each element x ∈ X there is an associated subset K(x) of elements of Y (which are covered in some sense by the element x). We know that ∪_x∈X K(x) = Y; our task is to find a subset X₀ ⊆ X of minimum cardinality such that ∪_x∈x0 K(x) = Y.

The set X is called the covering set and the set Y is the covered set. Every subset X′ ⊆ X satisfying ∪_x∈X′K(x) = Y is called a covering of Y by X. Our problem is to find a covering consisting of as few elements as possible, a minimum covering of Y by X. As an example we might take X to be the set of all matchings in a bipartite graph G, Y to be the set of edges E(G), and K(M) = M for each matching M ∈ X. Then a proper Δ(G)-colouring of G induces a minimum covering of Y by X. There are many other possible such examples, several are given in the exercises for this section. Later, in Section 12.2, we will consider covering the edges of a non-bipartite graph with bipartite subgraphs with prescribed properties. First, however, there are several special forms of coverings for bipartite graphs which merit particular attention.