No-homomorphism conditions for hypergraphs

Document Type : Research Paper


Faculty of Mathematical Sciences Shahrood university of Technology, Shahrood, Shahrood, Iran.


In this paper, we define some new homomorphism-monotone parameters for hypergraphs. Using these parameters, we extend some graph homomorphism results to hypergraph case. Also, we present some bounds for some well-known invariants of hypergraphs such as fractional chromatic number,independent numer and some other invariants of hyergraphs, in terms of these parameters.


[1] M. Alishahi and S. Tahmasebi, On circular chromatic number and chromatic number of some generalized
Kneser hypergraph, To appear, Ars Combinatoria.
[2] M. Alishahi and A. Taherkhani, A note on chromatic sum, Ars Combinatoria. Vol. CXVI (2014), pp. 49-54.
[3] M. Alishahi and H. Hajiabolhassan, Circular coloring and Mycielski construction, Discrete mathematics.
vol. 310, pp.1544-1550.
[4] J.A. Bondy and P. Hell, A note on the star chromatic number, Graph Theory. vol. 14 (1990),pp. 479-482.
[5] A.Daneshgar and H.Hajiabolhassan, Graph homomorphisms through random walks, J. Graph Theory. vol.
44 (2003),pp. 15-38.
[6] A. Daneshgar and H. Hajiabolhassan, Graph homomorphisms and nodal domains, Linear Algebra Appl.
vol. 418 (2006),pp. 44-52.
[7] A. Daneshgar and H. Hajiabolhassan, Density and power graphs in graph homomorphism problem, Discrete Mathematics. vol. 308 (2008), pp. 4027-4030.
[8] G. Hahn and C. Tardif, Graph homomorphisms: Structure and symmetry, in:G. Hahn,G.Sabidussi(Eds.)
Graph Symmetry, in:, NATO Adv. Sci. Inst. Sci. Inst. Ser. C Math. Phys.Sci., no. 497, Kluwer, Dordrecht.
(1997),pp. 107-167.
[9] P. Hell and J. Nesetril, Graph and homomorphisms, in:, Oxford Lecture Series in Mathematics and its
Applications, vol. 28, Oxford University press, Oxford. (2004).
[10] H. Hajiabolhassan, On colorings of graph powers, Discrete Mathematics. vol. 310 (2009),pp. 4299-4305.
[11] H. Hajiabolhassan and A. Taherkhani, Graph powers and Graph homomorphism, Discrete Mathematics.
vol. 310 (2010),pp. 4299-4305.
[12] S. Rahimi Sharbaf and Kh. Erfani, On the edge-di erence and edge-sum chromatic sum of the simple
graphs,Algebraic structures and their applications. vol. 4 (2017),pp. 33-42.