Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 044.38203
Autor: de Bruijn, N.G.; Erdös, Pál
Title: A colour problem for infinite graphs and a problem in the theory of relations. (In English)
Source: Nederl. Akad. Wet., Proc., Ser. A 54, 371-373 (1951); Indag. Math. 13, 371-373 (1951).
Review: Using a theorem of R. Rado (Zbl 033.25302), the authors give very simple proofs for three theorems announced in a previous paper [Erdös, Zbl 039.04902]. Theorem 1 states that if any finite subgraph of a graph G is k colourable, then G is k-colourable itself. (For a positive integer k a graph is called k-colourable if to each vertex one of a given set of k colours can be attached in such a way that on each edge the two end-points get different colours.)
Let S be a set, and assume that to every element a in S a subset f(a) \subseteq S-a is given. Two elements a and b of S are called independent if a in S-f(b) and b in S-f(a). A subset of S is called independent if any two elements of the subset are independent. The empty set and the subsets containing only one element are also called independent. The other two theorems are the following. If f(a) contains at most k elements for each a in S, then S is the union of 2k+1 independent sets. If f(a) is finite for each a in S, then S is the union of a countable number of independent sets.
Reviewer: T.Szele
Classif.: * 05C15 Chromatic theory of graphs and maps
05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag