Some examples of covering problems

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

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.