Ramsey-finiteness for graph pairs: A complete solution to the Burr-Erdős-Faudree-Schelp conjectures
Yaping Mao · 2026
Read Ramsey-finiteness for graph pairs: A complete solution to the Burr-Erdős-Faudree-Schelp conjectures by Yaping Mao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-17356.txt.
Description
Mao settles two conjectures from 1981 on Ramsey-finiteness for pairs of graphs, due to Burr, Erdős, Faudree, Rousseau, and Schelp. Mao proves that adjoining disjoint matchings preserves Ramsey-finiteness, and shows finiteness survives only in narrow cases: pairs of odd stars, pairs with a two-vertex component, and Faudree's star-forest family. Mao also corrects Burr's stronger 1979 survey claim with the true necessary-and-sufficient form. The result closes a long-standing classification question for graph pairs.
Catalog record
| CREATOR | Yaping Mao |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19361 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.17356