Coverings
Armen S. Asratian, Tristan M. J. Denley, Roland Häggkvist · Cambridge University Press eBooks · 1998
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 0 ⊆ 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.