Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8900566 | Applied Mathematics and Computation | 2018 | 5 Pages |
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
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Tingting Li, Xia Zhang,