A000789 Maximal order of a triangle-free cyclic graph with no independent set of size n.

2, 5, 8, 13, 16, 21, 26, 35, 38, 45, 48

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• hard
• more

Comments

Previous name was: Ramsey numbers.

The sequence may be considered as consisting of a special kind of Ramsey numbers. It is related to the ordinary two-color Ramsey numbers R(3,n), given in A000791, by the relation a(n) <= A000791(n)-1 as proved by Kalbfleisch. He also calculated the first eight terms, and noted that the inequality sometimes is strict. The first n for which this happens is n=6.

The terms a(10), a(11) and a(12) were calculated by Harborth and Krause. - Jörgen Backelin, Jan 07 2016

Examples

			That a(6) >= 16 is seen from the cyclic (or circulant) graph on 16 vertices, with edges between vertices of index distances 1, 3, or 8, since this cyclic graph indeed is triangle-free and has independence number five, which is less than six.
On the other hand, a(6) < 17, since any triangle free graph with independence number less than six and at least 17 vertices has exactly 17 vertices and cannot be regular, but all cyclic graphs are regular.
Thus, indeed, a(6) = 16.
		

References

• H. Harborth, S. Krause: Ramsey Numbers for Circulant Colorings, Congressus Numerantium 161 (2003), pp. 139-150.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• J. G. Kalbfleisch, Construction of special edge-chromatic graphs, Canad. Math. Bull., 8 (1965), 575-584.

Crossrefs

Cf. A000791.

Extensions

New title and a(10), a(11), a(12) added by Jörgen Backelin, Jan 12 2016