Opuscula Math. 40, no. 2 (2020), 271-290

Opuscula Mathematica

Subdivision of hypergraphs and their colorings

Moharram N. Iradmusa

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.
  • Moharram N. Iradmusa
  • Department of Mathematical Sciences, Shahid Beheshti University G.C., P. O. Box: 19839-63113, Tehran, Iran
  • Communicated by Gyula O.H. Katona.
  • Received: 2019-09-19.
  • Revised: 2020-01-14.
  • Accepted: 2020-01-16.
  • Published online: 2020-03-09.
Opuscula Mathematica - cover

Cite this article as:
Moharram N. Iradmusa, Subdivision of hypergraphs and their colorings, Opuscula Math. 40, no. 2 (2020), 271-290, https://doi.org/10.7494/OpMath.2020.40.2.271

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.