A394564 Least integer a(n) such that every graph on a(n) vertices has an induced regular subgraph of order n.

1, 2, 6, 8, 21

Offset

1,2

Comments

a(6)>=28 and a(7)>=71. It is not known if the sequence is increasing.

Links

Table of n, a(n) for n=1..5.

Paul W. Dyson and Brendan D. McKay, Ramsey numbers for regular induced subgraphs, arXiv:2604.08215 [math.CO] (2026).

Paul Dyson and Brendan McKay, Ramsey Graphs (section Regular induced subgraphs)

S. Fajtlowicz, T. McColgan, T. Read, and W. Staton, Ramsey numbers for induced regular subgraphs, Ars Combinatoria, 39 (1995) 149-154.

Example

a(3)=6 because some graphs with 5 vertices (for example the 5-cycle) have no induced regular subgraph of order 3, but every graph with 6 vertices has one.

Crossrefs

Cf. A394563, A394574, A390257.

Sequence in context: A290213 A058775 A103023 * A341732 A111247 A045656

Adjacent sequences: A394561 A394562 A394563 * A394565 A394566 A394567

Keyword

nonn,hard,more

Author

Brendan McKay, Mar 24 2026

Status

approved