Subdivision of hypergraphs and their colorings. (English) Zbl 1437.05073

Summary: 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.


05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI


[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,
[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, Ra
[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. · Zbl 0391.05028
[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
[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, · Zbl 0968.51016
[8] A. Ene, J. Vondrák,Hardness of submodular cost allocation: lattice matching and a simplex coloring conjecture, Approximation, randomization, and combinatorial optimization, · Zbl 1359.68100
[9] P. Erdős, A. Hajnal,On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar17(1966), 61-99. · Zbl 0151.33701
[10] T. Eschbach, W. Günther, B. Becker,Orthogonal hypergraph drawing for improved visibility, J. Graph Algorithms Appl.10(2006) 2, 141-157. · Zbl 1161.68665
[11] M.N. Iradmusa,On colorings of graph fractional powers, Discrete Math.310(2010) 10-11, 1551-1556. · Zbl 1214.05027
[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 · Zbl 1222.05067
[13] D.N. Kozlov,Chromatic subdivision of a simplicial complex, Homology Homotopy Appl., 14(2012) 2, 197-209. · Zbl 1259.68146
[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 · Zbl 0701.92023
[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 · Zbl 1371.05094
[16] F. Mohammadi, V. Welker,Combinatorics and algebra of geometric subdivision operations, [in:] Computations and combinatorics in commutative algebra, 77-122, Lecture · Zbl 1369.05225
[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, · Zbl 0584.05042
[20] V.I. Voloshin,Introduction to Graph and Hypergraph Theory, Nova Science Publishers, Inc., New York, 2009. · Zbl 1209.05002
[21] Y. Xue, T.P.-Y. Yu, T. Duchamp,Jet subdivision schemes on thek-regular complex, Comput. Aided Geom. Design23(2006) 4, 361-396. · Zbl 1097.65042
[22] R. Zaare-Nahandi,
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.