Polychromatic colorings and cover decompositions of hypergraphs

Tingting Li and Xia Zhang

Applied Mathematics and Computation, 2018, vol. 339, issue C, 153-157

Abstract: A polychromatic coloring of a hypergraph is a coloring of its vertices in such a way that every hyperedge contains at least one vertex of each color. A polychromatic m-coloring of a hypergraph H corresponds to a cover m-decomposition of its dual hypergraph H*. The maximum integer m that a hypergraph H admits a cover m-decomposition is exactly the longest lifetime for a wireless sensor network (WSN) corresponding to the hypergraph H. In this paper, we show that every hypergraph H has a polychromatic m-coloring if m≤⌊Sln(cΔS2)⌋, where 0 < c < 1, and Δ ≥ 1, S ≥ 2 are the maximum degree, the minimum size for all hyperedges in H, respectively. This result improves a result of Henning and Yeo on polychromatic colorings of hypergraphs in 2013, and its dual form improves one of Bollobás, Pritchard, Rothvoß, and Scott on cover decompositions of hypergraphs in 2013. Furthermore, we give a sufficient condition for a hypergraph H to have an “equitable” polychromatic coloring, which extends the result of Henning and Yeo in 2013 and improves in part one of Beck and Fiala in 1981 on 2-colorings (property B) of hypergraphs.

Keywords: Property B; Polychromatic coloring; Cover decomposition; Hypergraph (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300318305770
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:339:y:2018:i:c:p:153-157

DOI: 10.1016/j.amc.2018.07.019

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().