Abstract
- In this paper, we establish bounds for the chromatic number and the number of proper Acolourings of a uniform hypergraph. In particular, we improve and generalize results of Lazebnik [6J and the present author [3J. Besides we give a new proof of a theorem of Herzog and Schonheim [5J. Throughout this paper, a hypergmph is a set of non-empty subsets of some finite set. The elements of UEEH E resp. H are the vertices resp. edges of the hypergraph. For each hypergraph H, n(H) resp. m(H) stands for the number of vertices resp. edges. A loop is an edge of cardinality 1. H is r-uniform, if all edges have cardinality r. A chain (of length I) in a hypergraph H is a sequence S = (VI, El , ..• , Er, VI+I) such that VI, ... , VI resp. E l , •.• , EI are pairwise distinct vertices resp. edges and Vi, Vi+l E Ei for i = 1, ... , I; S is called a cycle (of length I), if I > 1 and VI+1 = VI' The girth of H, denoted by g(H), is defined as the length of a shortest cycle in H, if H is not cycle-free; otherwise g(H):= +00. We write x ~H y if there is a chain (x, . .. , y) in H. Obviously, this defines an equivalence relation on the vertex-set of H. Each class C E (UEEH E)j ~H is called a connected component of H. For abbreviation, define c(H) := I (UEEH E)j ~HI. For any A E IN, a A-colouring of a hypergraph H is a mapping of the vertex-set of H into {I, ... , A}. A A-colouring is proper, if all monochromatic edges are loops. By PH (A ) we denote the number of proper A-colourings of H. The chromatic number of H, denoted by x( H), is defined as the smallest A E IN such that PH(A) > O. The quantity PH ( A) turns out to be a polynomial in A, generalizing the chromatic polynomial of a graph. It has been investigated by the present author [2, 4J.