Research article

Polychromatic colorings of hypergraphs with high balance

  • Received: 01 October 2019 Accepted: 16 March 2020 Published: 20 March 2020
  • MSC : 05C15, 05C65

  • Let $m$ be a positive integer and $C = \{1, 2, \dots, m\}$ be a set of $m$ colors. A polychromatic $m$-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 in $C$. This problem is a generalization of $2$-colorings of hypergraphs and has close relations with the longest lifetime problem for a wireless sensor network, cover decompositions problem of hypergraphs and vertex cover problem of hypergraphs. In this paper, a main work is to find the maximum $m$ that a hypergraph $H$, with $n$ hyperedges, admits a polychromatic $m$-coloring such that each color appears at least $k$ times on each hyperedge. A $2\ln n$ approximation to the number is obtained when $k$ is a fixed positive integer. For the case that $k = O(n\ln n)$, there exists an $O(\ln n)$ approximation algorithm; for the case that $k = \omega (n\ln n)$, there exists a $(2+\sqrt{3})k$ approximation algorithm.

    Citation: Zhenzhen Jiang, Jun Yue, Xia Zhang. Polychromatic colorings of hypergraphs with high balance[J]. AIMS Mathematics, 2020, 5(4): 3010-3018. doi: 10.3934/math.2020195

    Related Papers:

  • Let $m$ be a positive integer and $C = \{1, 2, \dots, m\}$ be a set of $m$ colors. A polychromatic $m$-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 in $C$. This problem is a generalization of $2$-colorings of hypergraphs and has close relations with the longest lifetime problem for a wireless sensor network, cover decompositions problem of hypergraphs and vertex cover problem of hypergraphs. In this paper, a main work is to find the maximum $m$ that a hypergraph $H$, with $n$ hyperedges, admits a polychromatic $m$-coloring such that each color appears at least $k$ times on each hyperedge. A $2\ln n$ approximation to the number is obtained when $k$ is a fixed positive integer. For the case that $k = O(n\ln n)$, there exists an $O(\ln n)$ approximation algorithm; for the case that $k = \omega (n\ln n)$, there exists a $(2+\sqrt{3})k$ approximation algorithm.


    加载中


    [1] N. Alon, R. Berke, K. Buchin, et al. Polychromatic colorings of plane graphs, Discrete Comput. Geom., 42 (2009), 421-442. doi: 10.1007/s00454-009-9171-5
    [2] M. Axenovich, J. Goldwasser, R. Hansen, et al. Polychromatic colorings of complete graphs with respect to 1-, 2-factors and Hamiltonian cycles, J. Graph Theory, 87 (2018), 660-671. doi: 10.1002/jgt.22180
    [3] V. K. Bagaria, A. Pananjady, R. Vaze, Optimally approximating the coverage lifetime of wireless sensor networks, IEEE ACM T. Network., 25 (2017), 98-111. doi: 10.1109/TNET.2016.2574563
    [4] J. Beck and T. Fiala, Integer-making theorems, Discrete Appl. Math., 3 (1981), 1-8. doi: 10.1016/0166-218X(81)90022-6
    [5] B. Bollobás, D. Pritchard, T. Rothvoß, et al. Cover-decomposition and polychromatic numbers, SIAM J. Discrete Math., 27 (2013), 240-256. doi: 10.1137/110856332
    [6] P. Bose, D. Kirkpatrick, Z. Li, Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces, Comput. Geom. Theory Appl., 26 (2003), 209-219. doi: 10.1016/S0925-7721(03)00027-0
    [7] A. Buchsbaum, A. Efrat, S. Jain, et al. Restricted strip covering and the sensor cover problem, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (2007), 1056-1063.
    [8] M. Cardei, D. Du, Improving wireless sensor network lifetime through power aware organization, Wirel. Netw., 11 (2005), 333-340. doi: 10.1007/s11276-005-6615-6
    [9] X. Chen, Z. Du, J. Meng, Coloring and the Lovász Local Lemma, Appl. Math. Lett., 23 (2010), 219-221. doi: 10.1016/j.aml.2009.02.008
    [10] P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Colloquia Mathematica Societatis János Bolyai 10. Infinite and finite sets, Keszthely (HUNGARY), 1973.
    [11] R. Gupta, On decompositions of multigraph into spanning subgraphs, Bull. Amer. Math. Soc., 80 (1974), 500-502. doi: 10.1090/S0002-9904-1974-13468-3
    [12] R. Gupta, On the chromatic index and the cover index of a multigraph. In: Theory and Applications of Graphs, Springer, Berlin, 1978.
    [13] M. Henning, A. Yeo, 2-colorings in k-regular k-uniform hypergraphs, Eur. J. Combin., 34 (2013), 1192-1202. doi: 10.1016/j.ejc.2013.04.005
    [14] A. Hilton, Coloring the edges of a multigraph so that each vertex has at most j, or at least j edges of each color on it, J. Lond. Math. Soc., 12 (1975), 123-128. doi: 10.1112/jlms/s2-12.1.123
    [15] A. Hilton and D. de Werra, A sufficient condition for equitable edgecoloring of simple graphs, Discrete Math., 128 (1994), 179-201. doi: 10.1016/0012-365X(94)90112-0
    [16] S. Ianson, T. Łuczak, A. Rucinski, Random Graphs, Wiley, New York, 2000.
    [17] T. Li, X. Zhang, Polychromatic colorings and cover decompositions of hypergraphs, Appl. Math. Comput., 339 (2018), 153-157.
    [18] H. Ma, X. Zhang, Some class 1 graphs on gc-colorings, Acta Math. Sin., English Series, 32 (2016), 1237-1245. doi: 10.1007/s10114-016-5519-y
    [19] B. Mohar, R. Škrekovski, The Grötzsch theorem for the hypergraph of maximal cliques, Electron. J. Combin., 6 (1999), R26. doi: 10.37236/1458
    [20] H. Song and G. Liu, On f-edge cover-coloring of graphs, Acta Math. Sin., 48 (2005), 919-928.
    [21] S. Vishwanathan, On 2-coloring certain k-uniform hypergraphs, J. Comb. Theory A, 101 (2003), 168-172. doi: 10.1016/S0097-3165(02)00024-9
    [22] C. Xu, G. Liu, Edge covered critical multigraphs, Discrete Math., 308 (2008), 6348-6354. doi: 10.1016/j.disc.2007.12.003
    [23] C. Xu, G. Liu, A note on edge cover chromatic index of multigraphs, Discrete Math., 308 (2008), 6564-6568. doi: 10.1016/j.disc.2007.11.049
    [24] X. Zhang, Disconnected gc-critical graphs, J. Comb. Optim., 34 (2017), 771-780. doi: 10.1007/s10878-016-0108-7
    [25] X. Zhang, G. Liu, Equitable edge-colorings of simple graphs, J. Graph Theory, 66 (2011), 175-197. doi: 10.1002/jgt.20499
    [26] Y. Zhang, X. Zhang, On gc-colorings of nearly bipartite graphs, Czech. Math. J., 68(2018), 433-444. doi: 10.21136/CMJ.2018.0477-16
  • Reader Comments
  • © 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(2893) PDF downloads(278) Cited by(1)

Article outline

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog