Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 569.05041
Autor: Erdös, Paul; Nesetril, J.; Rödl, Vojtech
Title: Selectivity of hypergraphs. (In English)
Source: Finite and infinite sets, 6th Hung. Combin. Colloq., Eger/Hung. 1981, Vol. I, Colloq. Math. Soc. János Bolyai 37, No.1, 265-284 (1984).
Review: [For the entire collection see Zbl 559.00001.]
The concept of a selective hypergraph is introduced. Some results concerning the smallest number of edges needed for a selective k-graph are provided. They are similar to those for the B-property. It is shown that the minimal chromatic number of a selective graph H equals \chi(H) = (\chi(G)-1)(|V(G)|-1)+1. A construction of selective hypergraphs without short cycles is also given. The paper ends with the following result. For each K-graph G there exists a selective k-graph H with \chi(H) given by the formula above. Besides, if the edges e1,...,eq form a cycle in H of length at most p \geq 2 then there exists a subgraph G' of H isomorphic to G, containing the edges e1,...,eq.
Reviewer: L.Zaremba
Classif.: * 05C65 Hypergraphs
Keywords: selective hypergraph; selective k-graph; chromatic number
Citations: Zbl 559.00001
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag