Hypergraph families with bounded edge cover or transversal number.(English)Zbl 0534.05052

The transversal number $$\tau$$, packing number $$\nu$$, covering number $$\rho$$, and strong stability number $$\alpha$$ of hypergraphs are studied. A family F of finite hypergraphs is $$\tau$$-bound ($$\rho$$-bound) if there exists a binding function f such that $$\tau$$ (H)$$\leq f(\nu(H))$$ ($$\rho$$ (H)$$\leq f(\alpha(H)))$$ for all $$H\in F$$. The existence of a binding function in case of various $$\tau$$-bound ($$\rho$$-bound) is given. It is essentially based on the exclusion of octahedron graphs. Hypergraph versions of the clique color theorem of A. Gyárfás [Infinite finite sets, Colloq. Honour Paul Erdős, Keszthely 1973, Colloq. Math. Soc. János Bolyai 10, 801-816 (1975; Zbl 0307.05111)] are presented. Further results concern Helly hypergraphs with $$C_ 4$$-free line-graph, c-forest hypergraphs, strong Helly hypergraphs, boxes, and polyominoes (cf. the paper of C. Berge, C. C. Chen, V. Chvátal and C. S. Seow [Combinatorica 1, 217-224 (1981; Zbl 0491.05048)]).
Reviewer: J.Plesník

MSC:

 05C65 Hypergraphs 05B40 Combinatorial aspects of packing and covering

Citations:

Zbl 0307.05111; Zbl 0491.05048
Full Text:

References:

 [1] C. Berge,Graphs and Hypergraphs, North-Holland 1973. [2] C. Berge, C. C. Chen, V. Chvatal andC. S. Seow, Combinatorial properties of polyominoes,Combinatorica 1 (1) (1981), 217–224. · Zbl 0491.05048 [3] P. Erdos, Graph theory and Probability II.,Canad. J. of Math. 13 (1961), 346–352. · Zbl 0097.39102 [4] P. Erdos andA. Hajnal, On chromatic number of graphs and set systems,Acta Math. Acad. Sci. Hung. 17 (1–2) (1966), 61–99. · Zbl 0151.33701 [5] C. Flament, Hypergraphes arborés,Discrete Math. 21 (1978), 223–227. · Zbl 0393.05039 [6] R. L. Graham, B. L. Rothschild andJ. H. Spencer,Ramsey Theory, John Wiley, 1980. [7] A. Gyárfás, Ramsey-type theorem and its application to relatives of Helly’s theorem,Periodica Math. Hung. 3 (3–4) (1973) 261–270. · Zbl 0271.05113 [8] A. Gyárfás, On Ramsey covering numbers,Coll. Math. Soc. J. Bolyai 10.,Infinite and finite sets, (1973), 801–816. [9] E. Gyori, A minimax theorem on intervals,to appear. [10] F. S. Roberts, On the boxicity and cubicity of a graph,Recent Progress in Combinatories, Proc. Third Waterloo Conf. on Combinatorics, New York, 1969, 301–310.
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.