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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page