Name
Abstract | ||
|---|---|---|
A colouring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one vertex of each colour; the polychromatic number is the maximum number of colours in such a colouring. Its dual, the cover-decomposition number, is the maximum number of disjoint hyperedge-covers. In geometric settings, there is extensive work on lower-bounding these numbers in terms of their trivial upper bounds (minimum hyperedge size & degree). Our goal is to get good lower bounds in natural hypergraph families not arising from geometry. We obtain algorithms yielding near-tight bounds for three hypergraph families: those with bounded hyperedge size, those representing paths in trees, and those with bounded VC-dimension. To do this, we link cover-decomposition to iterated relaxation of linear programs via discrepancy theory. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-23719-5_67 | european symposium on algorithms |
Keywords | DocType | Volume |
hypergraph family,natural hypergraph family,disjoint hyperedge-covers,cover-decomposition number,discrepancy theory,minimum hyperedge size,bounded hyperedge size,polychromatic number,maximum number,bounded vc-dimension,hypergraphs,probabilistic methods | Journal | 27 |
Issue | Citations | PageRank |
1 | 3 | 0.53 |
References | Authors | |
21 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Béla Bollobás | 1 | 2696 | 474.16 |
| David Pritchard | 2 | 3 | 0.53 |
| Thomas Rothvoß | 3 | 570 | 33.87 |
| Alex Scott | 4 | 251 | 40.93 |