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

CREATORYaping Mao
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE19361
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.17356

Browse the full library · About the Tower of Babel