Polychromatic colorings of hypergraphs with high balance

Zhenzhen Jiang; Jun Yue; Xia Zhang; Zhenzhen Jiang; Jun Yue; Xia Zhang

doi:10.3934/math.2020195

AIMS Mathematics

2020, Volume 5, Issue 4: 3010-3018. doi: 10.3934/math.2020195

Previous Article Next Article

Research article

Polychromatic colorings of hypergraphs with high balance

School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, P. R. China

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.
- hypergraph,
- polychromatic coloring,
- cover decomposition,
- balanced coloring,
- probabilistic method
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:

Abstract

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.

References

[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 g_c-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 g_c-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 g_c-colorings of nearly bipartite graphs, Czech. Math. J., 68(2018), 433-444. doi: 10.21136/CMJ.2018.0477-16

Reader Comments

Your name:*

Email:*
© 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)