Opuscula Math. 40, no. 2 (2020), 271-290
https://doi.org/10.7494/OpMath.2020.40.2.271

Opuscula Mathematica

Subdivision of hypergraphs and their colorings

Abstract. In this paper we introduce the subdivision of hypergraphs, study their properties and parameters and investigate their weak and strong chromatic numbers in various cases.

Keywords: hypergraph, uniform hypergraph, subdivision of hypergraph.

Mathematics Subject Classification: 05C15.

Full text (pdf)

1. G. Agnarsson, M.M. Halldórsson, Strong colorings of hypergraphs, [in:] Approximation and online algorithms, Lecture Notes in Comput. Sci., vol. 3351, Springer, Berlin, 2005, 253-266.
2. I. Anderson, A First Course in Discrete Mathematics, Springer Undergraduate Mathematics Series, Springer-Verlag London Ltd., London, 2001.
3. G. Bacsó, C. Bujtás, Zs. Tuza, V. Voloshin, New challenges in the theory of hypergraph coloring, [in:] Advances in discrete mathematics and applications: Mysore, 2008, Ramanujan Math. Soc. Lect. Notes Ser., vol. 13, Ramanujan Math. Soc., Mysore, 2010, 45-57.
4. C. Berge, Graphs and Hypergraphs, revised ed., North-Holland Publishing Co., Amsterdam, 1976, Translated from the French by Edward Minieka, North-Holland Mathematical Library, vol. 6.
5. J.A. Bondy, U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, New York, 2008.
6. M. Brinkmeier, J. Werner, S. Recknagel, Communities in graphs and hypergraphs, [in:] Proceedings of International Conference on Information and Knowledge Management (2007), 869-872.
7. H. Edelsbrunner, D.R. Grayson, Edgewise subdivision of a simplex, ACM Symposium on Computational Geometry (Miami, FL, 1999), Discrete Comput. Geom. 24 (2000) 4, 707-719.
8. A. Ene, J. Vondrák, Hardness of submodular cost allocation: lattice matching and a simplex coloring conjecture, Approximation, randomization, and combinatorial optimization, 144-159, Leibniz Int. Proc. Inform., 28, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2014.
9. P. Erdős, A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar 17 (1966), 61-99.
10. T. Eschbach, W. Günther, B. Becker, Orthogonal hypergraph drawing for improved visibility, J. Graph Algorithms Appl. 10 (2006) 2, 141-157.
11. M.N. Iradmusa, On colorings of graph fractional powers, Discrete Math. 310 (2010) 10-11, 1551-1556.
12. A.V. Kostochka, M. Kumbhat, V. Rödl, Coloring uniform hypergraphs with small edge degrees, [in:] Fete of combinatorics and computer science, Bolyai Soc. Math. Stud. 20 (2010), Janos Bolyai Math. Soc., Budapest, 213-238.
13. D.N. Kozlov, Chromatic subdivision of a simplicial complex, Homology Homotopy Appl., 14 (2012) 2, 197-209.
14. J.R. Lundgren, Food webs, competition graphs, competition common enemy graphs and niche graphs, Applications of Combinatorics and Graph Theory to the Biological and Social Sciences 17 (1989), 221-243.
15. M. Mirzakhani, J. Vondrák, Sperner's colorings, hypergraph labeling problems and fair division, [in:] Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 873-886, SIAM, Philadelphia, PA, 2015.
16. F. Mohammadi, V. Welker, Combinatorics and algebra of geometric subdivision operations, [in:] Computations and combinatorics in commutative algebra, 77-122, Lecture Notes in Math., 2176, Springer, Cham, 2017.
17. E. Ramadan, A. Tarafdar, A. Pothen, A hypergraph model for the yeast protein complex network, [in:] 18th Parallel and Distributed Processing Symposium, 189-190, 2004.
18. G. Sander, Layout of directed hypergraphs with orthogonal hyperedges, [in:] GD 2004, LNCS, vol. 3393, 381-386, Springer, Heidelberg, 2004.
19. Zs. Tuza, V. Voloshin, Problems and results on colorings of mixed hypergraphs, [in:] Horizons of combinatorics, Bolyai Soc. Math. Stud., vol. 17, Springer, Berlin, 2008, 235-255.
20. V.I. Voloshin, Introduction to Graph and Hypergraph Theory, Nova Science Publishers, Inc., New York, 2009.
21. Y. Xue, T.P.-Y. Yu, T. Duchamp, Jet subdivision schemes on the $$k$$-regular complex, Comput. Aided Geom. Design 23 (2006) 4, 361-396.
22. R. Zaare-Nahandi, Invariance of the barycentric subdivision of a simplicial complex, Bull. Iranian Math. Soc. 38 (2012) 2, 423-432.
• Department of Mathematical Sciences, Shahid Beheshti University G.C., P. O. Box: 19839-63113, Tehran, Iran
• Communicated by Gyula O.H. Katona.
• Revised: 2020-01-14.
• Accepted: 2020-01-16.
• Published online: 2020-03-09.