Abstract
It is NP-Hard to find a proper 2-coloring of a given 2-colorable (bipartite) hypergraph H. We consider algorithms that will color such a hypergraph using few colors in polynomial time. The results of the paper can be summarized as follows: Let n denote the number of vertices of H and m the number of edges, (i) For bipartite hypergraphs of dimension k there is a polynomial time algorithm which produces a proper coloring using min\(\{ O(n^{1 - 1/k} ),O((m/n)^{\tfrac{1}{{k - 1}}} )\}\)colors, (ii) For 3-uniform bipartite hypergraphs, the bound is reduced to O(n 2/9). (iii) For a class of dense 3-uniform bipartite hypergraphs, we have a randomized algorithm which can color optimally. (iv) For a model of random bipartite hypergraphs with edge probability pā„ dn ā2, d > O a sufficiently large constant, we can almost surely find a proper 2-coloring.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F.Alizadeh, Combinatorial Optimizations with Semi-definite matrices, 2nd Conference of Integer Programming and Combinatorial Optimizations (1992). pp385ā405.
N.Alon, N.Kahale, A spectral technique for coloring random 3-colorable graphs, DIMACS TR-94-35.
N.Alon, J.Spencer. The Probabilistic Method, John Wiley & Sons (1992).
J.Beck, An algorithmic approach to LovĆ”sz Local Lemma I, Random Structures & Algorithms (1991). pp343ā365.
K. Edwards, The complexity of coloring problems on dense graphs, Theoretical Computer Science 43 (1986) 337ā343.
M.Goemans, D.Williamson, .878-Approximation Algorithms for MAX CUT and MAX 2SAT. Proceedings of the 26th ACM Symposium on Theory of Computing (1994).
D.Karger, R.Motwani, M.Sudan, Approximation Graph Coloring by Semidefinite Programming. 35th Foundations of Computer Science (1995). pp2ā13.
J.Kahn, SzemerĆ©di, J.Friedman,On the second eigenvalue in random regular graphs, Proceedings of the 21st ACM STOC (1989). pp 587ā598.
L. LovĆ sz, Covering and coloring of hypergraphs, Preceding of the 4th Sourtheastern Conference on Combinatorics, Graph Theory and Computing. Utilitas Mathematica Publishing. Winnipeg (1973). pp 3ā12.
C.J.H McDiarmid, A random recoloring method for graph and hypergraph, Combinatorial Probability and Computing 2 (1993). pp 363ā365.
G.Strang, Linear algebra and its applications, Hardcourt Brace Jovanovich Publishing (1988).
A. Widgerson, Improving the performance gurantee of approximate graph coloring, Journal of ACM 30 (1983). PP 729ā735.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
Ā© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, H., Frieze, A. (1996). Coloring bipartite hypergraphs. In: Cunningham, W.H., McCormick, S.T., Queyranne, M. (eds) Integer Programming and Combinatorial Optimization. IPCO 1996. Lecture Notes in Computer Science, vol 1084. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61310-2_26
Download citation
DOI: https://doi.org/10.1007/3-540-61310-2_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61310-7
Online ISBN: 978-3-540-68453-4
eBook Packages: Springer Book Archive