A123441 Number of P_4-sparse perfect graphs on n nodes.

1, 2, 4, 11, 27, 78, 218, 653, 1963, 6088, 19078, 60825, 195757, 636810, 2087764, 6896119

Offset

1,2

Comments

A graph is P_4-sparse if no set of 5 vertices induces a subgraph that contains two or more induced P_4 (path on 4 vertices). P4-sparse graphs are perfect. - Falk Hüffner, Dec 01 2015

References

C. T. Hoàng, Perfect graphs, Ph.D. Thesis, School of Computer Science, McGill University, Montreal, Canada, 1985.

Links

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

S. Hougardy, Home Page

S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 5926e72.

Crossrefs

Sequence in context: A123440 A071314 A309886 * A086441 A316696 A319616

Adjacent sequences: A123438 A123439 A123440 * A123442 A123443 A123444

Keyword

nonn

Author

N. J. A. Sloane, Oct 18 2006

Extensions

a(11)-a(16) added using tinygraph by Falk Hüffner, Jan 16 2016

Status

approved