Menu
A \((3,k,n,e)\) Ramsey graph is a triangle-free graph on \(n\) vertices with \(e\) edges and no independent set of size \(k\). Similarly, a \((3,k)\)-, \((3,k,n)\)-, or \((3,k,n,e)\)-graph is a \((3,k,n,e)\) Ramsey graph for some \(n\) and \(e\). In the first part of the paper, we derive an explicit formula for the minimum number of edges in any \((3,k,n)\)-graph for \(n\leq3(k-1)\), i.e., a partial formula for the function \(e(3,k,n)\) investigated in \([3,5,7]\). We prove some general properties of minimum \((3,k,n)\)-graphs with \(e(3,k,n)\) edges and present a construction of minimum \((3,k+1,3k-1,5k-5)\)-graphs for \(k\geq2\) and minimum \((3,k+1,3k,5k)\)-graphs for \(k\geq4\). In the second part of the paper, we describe a catalogue of small Ramsey graphs: all \((3,k)\)-graphs for \(k\leq6\) and some \((3,7)\)-graphs, including all \(191 (3,7,22)\)-graphs, produced by a computer. We present for \(k\leq7\) all minimum \((3,k,n)\)-graphs and all \(10\) maximum \((3,7,22)\)-graphs with \(66\) edges.