zbMATH — the first resource for mathematics

A contribution to the chromatic theory of uniform hypergraphs. (English) Zbl 0831.05029
Let \(H\) be a hypergraph and \(P_H (\lambda)\) denote the number of proper \(\lambda\)-colourings of \(H\), where ‘proper’ means that the only monochromatic edges are loops. For uniform hypergraphs \(H\), lower bounds and upper bounds on \(P_H (\lambda)\) are obtained in terms of the rank, the number of vertices and edges and some arbitrary number less than the girth. If \(H\) has \(m > 1\) edges and is uniform of rank \(r > 1\), it follows that \(\chi (H) \leq \lceil \root {r - 1} \of m \rceil\), where \(\chi (H)\) denotes the chromatic number of \(H\). It should be noted that the bounds on \(P_H (\lambda)\) are new for graphs, too.
Reviewer: K.Dohmen (Berlin)

05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
Full Text: DOI
[1] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam (1973).
[2] K. Dohmen, ’A Broken-Circuits-Theorem for hypergraphs’, Arch. Math. 64 (1995), 159–162. · Zbl 0813.05048
[3] K. Dohmen, ’Lower Bounds and Upper Bounds for Chromatic Polynomials’, J. Graph Theory 17 (1993), 75–80. · Zbl 0780.05023
[4] K. Dohmen, Chromatische Polynome von Graphen und Hypergraphen, Dissertation, Universität Düsseldorf (1993). · Zbl 0837.05057
[5] M. Herzog and J. Schonheim, ’The Br Property and Chromatic Numbers of Generalized Graphs’, J. Combin. Theory Ser. B 12 (1972), 41–49. · Zbl 0236.05123
[6] F. Lazebnik, ’New Upper Bounds for the Greatest Number of Proper Colorings of a ({\(\upsilon\)}, e)-Graph’, J. Graph Theory 14 (1990), 25–29. · Zbl 0688.05042
[7] L. Lovász, Combinatorial Problems and Exercises, North-Holland, Amsterdam (1979).
[8] I. Tomescu, ’Hypertrees and Bonferroni Inequalities’, J. Combin. Theory Ser. B 41 (1986), 209–217. · Zbl 0595.05055
[9] H. Whitney, ’A Logical Expansion in Mathematics’, Bull. Am. Math. Soc. 38 (1932), 572–579. · JFM 58.0605.08
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.