Journal article icon

Journal article

Cover-Decomposition and polychromatic numbers

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 and degree). Our goal is to get good lower bounds in natural h...

Expand abstract

Actions


Access Document


Authors


Bollobás, B More by this author
Pritchard, D More by this author
Journal:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume:
6942 LNCS
Pages:
799-810
Publication date:
2011
DOI:
EISSN:
1611-3349
ISSN:
0302-9743
URN:
uuid:f913f209-ab1d-41b8-8e3a-0e8372941b2e
Source identifiers:
322198
Local pid:
pubs:322198
Language:
English

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP