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

Gyárfás, A.; Lehel, J.

Combinatorica 3, 351-358 (1983).

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

Keywords:

transversal number; packing number; covering number; strong stability number; Helly hypergraphs

Citations:

Zbl 0307.05111; Zbl 0491.05048

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.