A390257 - OEIS

%I #30 Apr 16 2026 09:58:01

%S 0,1,2,2,2,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5

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

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

%H Thomas Bloom, <a href="https://www.erdosproblems.com/82">Erdős Problem 82</a>.

%H Paul W. Dyson and Brendan D. McKay, <a href="https://arxiv.org/abs/2604.08215">Ramsey numbers for regular induced subgraphs</a>, arXiv:2604.08215 [math.CO] (2026).

%H Paul Dyson and Brendan McKay, <a href="https://users.cecs.anu.edu.au/~bdm/data/ramsey.html">Ramsey Graphs</a> (section Regular induced subgraphs)

%H Erdős problems database contributors, <a href="https://github.com/teorth/erdosproblems/issues/94">Computations of F(n) and t(n) from #82</a>.

%H S. Fajtlowicz, T. McColgan, T. Reid, and W. Staton, <a href="https://combinatorialpress.com/ars-articles/volume-039-ars-articles/ramsey-numbers-for-induced-regular-subgraphs/">Ramsey numbers for induced regular subgraphs</a>, Ars Combinatoria, 39 (1995) 149-154.

%F a(n) = max{ k | A394563(k) <= n }. - _Brendan McKay_, Apr 11 2026

%e 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.

%Y Cf. A390256, A394563, A394564.

%K nonn,more

%O 0,3

%A _Boris Alexeev_, Oct 30 2025