Subdivision of hypergraphs and their colorings

• Autorzy: Iradmusa Moharram N.

Identyfikatory

DOI

10.7494/OpMath.2020.40.2.271

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

hypergraph; uniform hypergraph; subdivision of hypergraph

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2020
• Tom: Vol. 40, no. 2
• Strony: 271--290
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Iradmusa Moharram N.

• Department of Mathematical Sciences Shahid Beheshti University G.C. P. O. Box: 19839-63113, Tehran, Iran

Bibliografia

• [1] G. Agnarsson, M.M. Halldorsson, 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. Bacso, C. Bujtas, Zs. Tuza, V. Voloshin, New challenges in the theory of hypergraph coloring, [in:] Advances in discrete mathematics and applications: Mysore, 2008, Ra-manujan 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. Vondrak, Hardness of sub-modular 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. Erdos, A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar 17 (1966), 61-99.
• [10] T. Eschbach, W. Gunther, 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. Rodl, 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 simplidal 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. Vondrak, 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 simplidal complex, Bull. Iranian Math. Soc. 38 (2012) 2, 423-432.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).