bibkey: dyson2026regularinduced authors: Paul W. Dyson, Brendan D. McKay year: 2026 title: “Ramsey numbers for regular induced subgraphs” doi: 10.48550/arXiv.2604.08215 url: https://arxiv.org/abs/2604.08215v3 claim: “Exact values and bounds for the least n such that every n-vertex graph has a regular induced subgraph of order k; Section 4 gives prime-order constructions from disjoint unions of products C_r[K_s] and states their optimality within that class for p ≥ 13 as a belief.” strata_touched:

• D5/S3/Combinatorics/RegularInduced/DysonMcKay license: citation-only triage: anchor

Dyson and McKay, Ramsey numbers for regular induced subgraphs

The paper studies the smallest n for which every graph on n vertices contains a regular induced subgraph of order at least k, a problem of Erdős, Fajtlowicz and Staton. Section 4 gives explicit quadratic lower-bound constructions. Lemma 4.1 classifies the connected induced regular subgraphs of the lexicographic product C_r[K_s] for r ≥ 4, and Theorem 4.2 gives, for each prime p ≥ 5, a disjoint union G_p of such products with no induced regular subgraph of order p, of order 9(p−1)²/8, (p−1)(9p−7)/8 or (p−1)(9p−11)/8 according to p modulo 12. The authors state, without proof, that these graphs are optimal for p ≥ 13 within the class of disjoint unions of lexicographic products of cycles and cliques.

The module D5/S3/Combinatorics/RegularInduced/DysonMcKay proves this optimality.

Verified locator

DOI: 10.48550/arXiv.2604.08215

URL: https://arxiv.org/abs/2604.08215v3

• Locator: Section 4, Lemma 4.1, Theorem 4.2 and the sentence following it.