show/hide this revision's text 3 added 1747 characters in body

later Thanks to the answer from Brendan McKay (who would know!) I can say a bit more. I'll allow myself an editorial moment to say that the description of the graph6 format is not the most welcoming to the casual (windows based) curious reader who just wants to see the (adjacency matrix of) a particular graph or two. Hence I will state that the data pages he links to give descriptions of certain graphs but I have seen them. An R(4,4) graph is one which has neither 4 vertices with all 6 edges between them nor 4 vertices with 0 edges between them. Of course any subgraph of such a graph is also R(4,4). The definition in the question of a Quasi-Ramsey graph (for $n=4$) is an R(4,4) graph (on 16 vertices or less) so that no extension by adding one vertex and some edges on it is also R(4,4)

As Brendan says (with a link to a page with the descriptions) there is a single 17 vertex R(4,4) graph. It has only one 16 vertex subgraph . There is exactly one other 16 vertex R(4,4) graph so it fits the given description of Quasi-Ramsey. Between them these two graphs have no more that 32 vertex subgraphs (probably somewhat less.) In all there are evidently 640 15-vertex R(4,4) graphs so at least 608 of them are Quasi-Ramsey. Between all 640 there at most 640*15=9600 14-vertex subgraphs. Evidently there are 130816 14-vertex R(4,4) graphs so at least 130816-9600= 121216 of them are Quasi-Ramsey. Most likely some of those are not regular (let alone vertex transitive).

All this leads me to suspect that there are a very very large number of Quasi-Ramsey graphs for each $n \ge 5$ and that plenty of them are not regular. Perhaps someone can give an explicit description of at least one for $n=4$, however I can not at the moment.

show/hide this revision's text 2 added 398 characters in body

The complement of a quasi-Ramsey graph will still be quasi-Ramsey so that answers the question about non-isomorphic with the same number of variables (together with your construction).

$R(4,4)=18$ and there is a unique 17 vertex graph (a Paley graph) with no $K_4$ subgraph or 4 vertex independent set.It is self dual and regular of degree 8. It is vertex transitive which means that except for one 16 vertex graph every other either contains 4 independent vertices or a $K_4$ or is quasiRamsey. This should make it easy to find some irregular 16 vertex quasiRamsey graphs.

show/hide this revision's text 1

The complement of a quasi-Ramsey graph will still be quasi-Ramsey so that answers the question about non-isomorphic with the same number of variables (together with your construction).