##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 244.05114

**Autor: ** Chvatal, V.; Erdös, Paul; Hedrlin, Z.

**Title: ** Ramsey's theorem and self-complementary graphs. (In English)

**Source: ** Discrete Math. 3, 301-304 (1972).

**Review: ** A graph G is called s-good if neither G nor its complement contains a complete graph with s+1 vertices. By Ramsey's theorem, given any s there is the least integer n(s) such that no graph with more than n(s) vertices is s-good. Let n^*(s) be the largest number of vertices of a self-complementary s-good graph. Then n^*(s) \leq n(s). One has n^*(2) = n(2) = 5 and n^*(3) = n(3) = 17; perhaps n^*(s) = n(s) for all s. The authors prove n^*(st) \geq (n^*(s)-1)n(t); in particular, n^*(2t) \geq 4n(t). The last inequality together with an earlier exponential lower bound on n(s), due to Erdös, yields an exponential lower bound on n^*(s). An application to Shannon's notion of a capacity of G is mentioned.

**Classif.: ** * 05C99 Graph theory

05C35 Extremal problems (graph theory)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag