Cographs

A cograph or complement-reducible graph is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. An alternative and equivalent characterisation is that the class of cographs equals the class of P4-free graphs, i.e. graphs which do not contain a P4 as induced subgraph.

Below are the lists of connected cographs. These graphs were generated by Átila Jones using the generation algorithm described in [1]. The source code of this algorithm can be found here. The graph lists are currently only available in 'graph6' format. The larger files are compressed with gzip.

Connected cographs

Vertices No. of cographs
11
21
32
45
512
633
790
8261
9766
102312
117068
1221965
1368954
14218751
15699534
162253676
177305788
1823816743
1978023602
20256738751
21848152864
222811996972
239353366564
2431204088381
25104384620070
26350064856815
271176693361956
283963752002320

References

[1] A.A. Jones, F. Protti and R.R. Del-Vecchio, Cograph generation with linear delay, Theoretical Computer Science, 713:1-10, 2018.