A394462 - OEIS

%I #26 May 23 2026 10:52:26

%S 1,2,4,11,34,148,964,10472,191776,5524670,219302174,10333796899,

%T 493296884096,19658348081642

%N Number of graphs with n vertices that have no induced regular subgraph of order 6.

%C The sequence eventually becomes 0. It is known that a(27) >= 16, but it is not known whether a(28) > 0.

%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 S. Fajtlowicz, T. McColgan, T. Read, and W. Staton, <a href="https://combinatorialpress.com/article/ars/Volume%20039/volume-39-paper-15.pdf">Ramsey numbers for induced regular subgraphs</a>, Ars Combinatoria, 39 (1995) 149-154.

%e An example with 25 vertices is the lexicographic product of the pentagon with itself.

%Y Cf. A394573 (subgraphs of order 4), A394539 (order 5), A394930 (order 7), A392636 (order 6 or greater).

%K nonn,hard,more

%O 1,2

%A _Brendan McKay_, Mar 21 2026

%E a(14) from _Paul W. Dyson_, May 23 2026