Originators: P. Mani and J. Pach (presented by J. Cooper - REGS 2009)
Definitions: A k-covering of a set X is a family F of subsets of X such that each element of X appears in at least k sets in F. Viewed as a hypergraph, X is the vertex set, F is the edge set, and a k-covering of X is a hypergraph with minimum degree at least k.
Question: When can the edges of a k-covering be split into two 1-coverings?
Background: A simple example of a non-splittable 2-covering is the set of edges in an odd cycle; they form a non-splittable 2-covering of the vertices. Mani and Pach [MP] considered k-coverings of the cartesian plane in which the edges are unit disks. They asked whether any finite k suffices to guarantee a split into two 1-coverings. Pach claimed that k=33 is enough. Tardos and Tóth [TT] proved that when the edges are translates of a fixed open triangle, k=43 suffices. Pach [P] proved that whenever P is a centrally symmetric open convex polygon, there is a constant cP,r such that a k-covering splits into r 1-coverings whenever k>cP,r. Splitting is more difficult when the sizes of geometric objects may vary: Pach, Tardos, and Tóth [PTT] showed that no finite k suffices when strips, axis-parallel rectangles, or homethetes of any fixed quadrilateral are used as edges. There are many problems of this sort in geometric settings; see [PT].
In one direction, the problem generalizes to groups. Given a set S in a group Γ, one could define σ(S) to be the least k such that every k-covering of Γ by translates of S splits into two 1-coverings. In another direction, one can consider finite hypergraphs, such as the cliques in a graph, asking when a k-covering of the vertices by cliques splits into two 1-coverings. When G is a k-regular bipartite graph, the edges form a k-covering of the vertices and split into k 1-coverings. When the edges of the hypergraph are the vertex sets of stars in a graph, a split into 1-coverings is a "domatic partition" of the graph; in each 1-covering, the centers of the stars form a dominating set (see [FHKS]).
References:
[FHKS]
Feige, Uriel; Halldórsson, Magnús M.; Kortsarz,
Guy; Srinivasan, Aravind
Approximating the domatic number.
SIAM J. Comput. 32 (2002/03), no. 1, 172--195 (electronic).
[MP]
P. Mani, J. Pach, Decomposition problems for multiple coverings with unit
balls, manuscript, 1986.
[P] Pach, J. Covering the plane with convex polygons.
Discrete Comput. Geom. 1 (1986), no. 1, 73--81.
[PT] Pach, J; Tóth, G.;
Decomposition of multiple coverings into many parts.
Comput. Geom. 42 (2009), no. 2, 127--133.
[TT] Tardos, G.; Tóth, G.;
Multiple coverings of the plane with triangles.
Discrete Comput. Geom. 38 (2007), no. 2, 443--450.