Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.03572 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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\leq R(3, 10)\leq 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.