Cover-Decomposition and Polychromatic Numbers

Details Cover-Decomposition and Polychromatic Numbers Cover-Decomposition and Polychromatic Numbers

2010-09-30

arxiv.org/abs/1009.6144v2

Mathematics

Combinatorics

Merge of previous version with arXiv:1009.5893

Scientific paper

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 any polychromatic colouring. Its dual is the cover-decomposition number: 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 and minimum 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. One new technique we use is a link between cover-decomposition and iterated relaxation of linear programs.

Affiliated with

Also associated with

No associations

Rating

Cover-Decomposition and Polychromatic Numbers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cover-Decomposition and Polychromatic Numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cover-Decomposition and Polychromatic Numbers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-243331