A390257 Minimum size of maximum regular induced subgraph of a graph on n vertices.

0, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5

Offset

0,3

Comments

This is similar to Ramsey numbers, except we consider not only complete and independent subgraphs but any regular induced subgraph.

Links

Table of n, a(n) for n=0..20.

Thomas Bloom, Erdős Problem 82.

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)

Erdős problems database contributors, Computations of F(n) and t(n) from #82.

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

Formula

a(n) = max{ k | A394563(k) <= n }. - Brendan McKay, Apr 11 2026

Example

Every graph on 5 vertices either contains the complete graph on 3 vertices or its complement, or the graph is the 5-cycle which is itself regular. Moreover, the tree {13,23,34,45} has no regular induced subgraph greater than 3. So a(5)=3.

Crossrefs

Cf. A390256, A394563, A394564.

Sequence in context: A108504 A036468 A334051 * A345380 A367128 A028829

Adjacent sequences: A390254 A390255 A390256 * A390258 A390259 A390260

Keyword

nonn,more

Author

Boris Alexeev, Oct 30 2025

Status

approved