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

1, 2, 4, 11, 34, 148, 964, 10472, 191776, 5524670, 219302174, 10333796899, 493296884096, 19658348081642

Offset

1,2

Comments

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

Links

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

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

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

Crossrefs

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

Sequence in context: A344489 A238425 A392636 * A365578 A358075 A071115

Adjacent sequences: A394459 A394460 A394461 * A394463 A394464 A394465

Keyword

nonn,hard,more

Author

Brendan McKay, Mar 21 2026

Extensions

a(14) from Paul W. Dyson, May 23 2026

Status

approved