Polychromatic colorings and cover decompositions of hypergraphs
Polychromatic colorings and cover decompositions of hypergraphs
复制标题
超图的多色着色和覆盖分解
DOI：
10.1016/j.amc.2018.07.019
复制
发表时间：
2018-12
影响因子：
4
通讯作者：
Xia Zhang
中科院分区：
文献类型：
--
作者：
Tingting Li;Xia Zhang
一个超图的多色染色是指它的顶点的染色使得每一个超边至少包含一个每种颜色的顶点。超图H的多色m-染色对应于其对偶超图H* 的覆盖m-分解。超图H允许覆盖m-分解的最大整数m恰好是超图H所对应的无线传感器网络的最长生存期。本文证明了：当m≤，其中0< c< 1，Δ≥ 1，S≥ 2分别是H中所有超边的最大度和最小尺寸时，每个超图H都有多色m-染色.这个结果改进了Henning和Yeo在2013年关于超图的多色着色的结果，并且它的对偶形式改进了Bollobás，Pritchard，Rothvovich和Scott在2013年关于超图的覆盖分解的结果。进一步，我们给出了超图H具有“公平”多色染色的一个充分条件，推广了Henning和Yeo在2013年的结果，改进了Beck和Fiala在1981年的第一部分关于超图的2-染色（性质B）.
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≤⌊ S ln (c Δ S 2)⌋, 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.
登录
查看更多内容
DOI：
10.1016/j.aml.2009.02.008
发表时间：
2010-03
期刊：
Appl. Math. Lett.
影响因子：
--
作者：
Xing Chen;Zhihua Du;J. Meng
通讯作者：
Xing Chen;Zhihua Du;J. Meng
DOI：
--
发表时间：
--
期刊：
--
影响因子：
--
作者：
P. Erdos-L Lovász
通讯作者：
P. Erdos-L Lovász
DOI：
--
发表时间：
2006-05
期刊：
--
影响因子：
--
作者：
A. Buchsbaum;A. Efrat;Shaili Jain;Suresh Venkatasubramanian;Ke Yi
通讯作者：
A. Buchsbaum;A. Efrat;Shaili Jain;Suresh Venkatasubramanian;Ke Yi
DOI：
10.1007/978-3-642-23719-5_67
发表时间：
2010-09
期刊：
--
影响因子：
--
作者：
B. Bollobás;David Pritchard;T. Rothvoss;A. Scott
通讯作者：
B. Bollobás;David Pritchard;T. Rothvoss;A. Scott
DOI：
10.1016/j.ejc.2013.04.005
发表时间：
2013-10
期刊：
Eur. J. Comb.
影响因子：
--
作者：
Michael A. Henning;Anders Yeo
通讯作者：
Michael A. Henning;Anders Yeo