1604.03716

Total: 1

#1 Small minimal $(3, 3)$-Ramsey graphs [PDF] [Copy] [Kimi] [REL]

Author: Aleksandar Bikov

We say that $G$ is a $(3, 3)$-Ramsey graph if every $2$-coloring of the edges of $G$ forces a monochromatic triangle. The $(3, 3)$-Ramsey graph $G$ is minimal if $G$ does not contain a proper $(3, 3)$-Ramsey subgraph. In this work we find all minimal $(3, 3)$-Ramsey graphs with up to 13 vertices with the help of a computer, and we obtain some new results for these graphs. We also obtain new upper bounds on the independence number and new lower bounds on the minimum degree of arbitrary $(3, 3)$-Ramsey graphs.

Subject: Combinatorics

Publish: 2016-04-13 10:40:39 UTC