On structural properties of some probable $R(3,10)$-critical graphs

Abstract

The Ramsey number $R(s,t)$ is the smallest positive integer $n$ such that every graph on $n$ vertices contains either a clique of size $s$ or an independent set of size $t$. An $R(s,t)$-critical graph is a graph on $R(s,t)-1$ vertices that contains neither a clique of size $s$ nor an independent set of size $t$. It is known that $40\le R(3,10)\le 42$. We study the structure of a $R(3,10)$-critical graphs by assuming $R(3,10)=42$. We show that if such a graph exists then its minimum degree and vertex connectivity are the same and is $6,7$ or $8$. Then we find all the possible degree sequences of such graphs. Further, we show that if such a graph exists, then its diameter is either $2$ or $3$, and if it has diameter $2$ and minimum degree $6$, then it has only $21$ choices for its degree sequence.

arXiv comment14 pages