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

Iradmusa, Moharram N.

Opusc. Math. 40, No. 2, 271-290 (2020).

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.

MSC:

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

Keywords:

hypergraph; uniform hypergraph; subdivision of hypergraph

References:

[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,