Here we present some graphs related to classical Ramsey numbers.
A *Ramsey(s,t,n)-graph* is a graph with n vertices, no clique of
size s, and no independent set of size t. A *Ramsey(s,t)-graph* is
a Ramsey(s,t,n)-graph for some n. Ramsey Theory tells us that there are
only a finite number of Ramsey(s,t)-graphs for each s and t, but finding
all such graphs, or even determining the largest n for which they exist,
is a famously difficult problem.

For a survey of the latest results on Ramsey graphs, see Radziszowski's Dynamic Survey at the Electronic Journal of Combinatorics. For information on the data format used below, see the combinatorial data page.

1 vertex (1 graph)

2 vertices (2 graphs)

3 vertices (3 graphs)

4 vertices (6 graphs)

5 vertices (9 graphs)

6 vertices (15 graphs)

7 vertices (9 graphs)

8 vertices (3 graphs)

1 vertex (1 graph)

2 vertices (2 graphs)

3 vertices (3 graphs)

4 vertices (7 graphs)

5 vertices (13 graphs)

6 vertices (32 graphs)

7 vertices (71 graphs)

8 vertices (179 graphs)

9 vertices (290 graphs)

10 vertices (313 graphs)

11 vertices (105 graphs)

12 vertices (12 graphs)

13 vertices (1 graph)

1 vertex (1 graph)

2 vertices (2 graphs)

3 vertices (3 graphs)

4 vertices (7 graphs)

5 vertices (14 graphs)

6 vertices (37 graphs)

7 vertices (100 graphs)

8 vertices (356 graphs)

9 vertices (1407 graphs)

10 vertices (6657 graphs)

11 vertices (gzipped) (30395 graphs)

12 vertices (gzipped) (116792 graphs)

13 vertices (gzipped) (275086 graphs)

14 vertices (gzipped) (263520 graphs)

15 vertices (gzipped) (64732 graphs)

16 vertices (gzipped) (2576 graphs)

17 vertices (7 graphs)

21 vertices (gzipped) (1118436 graphs; found by Gunnar Brinkmann and Jan Goedgebeur)

22 vertices (191 graphs)

McKay and Zhang proved that the largest Ramsey(3,8)-graphs have 27 vertices in 1992, but the full set of Ramsey(3,8,27)-graphs was not determined until Gunnar Brinkmann and Jan Goedgebeur did it in 2012.

27 vertices (gzipped) (477142 graphs)

The maximal Ramsey(3,9)-graph has 35 vertices and was found by
Kalbfleisch long ago, but it took until 2013 for its uniqueness to
be proved. See the paper of Goedgebeur and Radziszowski.

35 vertices (1 graph)

1 vertex (1 graph)

2 vertices (2 graphs)

3 vertices (4 graphs)

4 vertices (9 graphs)

5 vertices (24 graphs)

6 vertices (84 graphs)

7 vertices (362 graphs)

8 vertices (2079 graphs)

9 vertices (14701 graphs)

10 vertices (gzipped) (103706 graphs)

11 vertices (gzipped) (546356 graphs)

12 vertices (gzipped) (1449166 graphs)

13 vertices (gzipped) (1184231 graphs)

14 vertices (gzipped) (130816 graphs)

15 vertices (640 graphs)

16 vertices (2 graphs)

17 vertices (1 graph)

McKay and Radziszowski proved that there are no Ramsey(4,5)-graphs with more than 24 vertices. The full set of Ramsey(4,5,24)-graphs has not been determined, but r45_24some.g6.gz contains the 350904 that are known.

In early 2012, Geoffrey Exoo raised the lower bound on R(4,6) by discovering 37 Ramsey(4,6,35)-graphs. There could be more, and there might even be some with 36-40 vertices. See r46_35some.g6.

Geoffrey Exoo found several Ramsey(5,5,42)-graphs in 1989. McKay and Radziszowski expanded this to 656 graphs and conjectured that there are none larger. However, there could be more with 42 vertices and even some with 43-48 vertices. r55_42some.g6 contains 328 of these graphs; the other 328 are their complements.

Page Master: Brendan McKay, bdm@cs.anu.edu.au and http://cs.anu.edu.au/~bdm.