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.
Vertices | No. of cographs |
---|---|
1 | 1 |
2 | 1 |
3 | 2 |
4 | 5 |
5 | 12 |
6 | 33 |
7 | 90 |
8 | 261 |
9 | 766 |
10 | 2312 |
11 | 7068 |
12 | 21965 |
13 | 68954 |
14 | 218751 |
15 | 699534 |
16 | 2253676 |
17 | 7305788 |
18 | 23816743 |
19 | 78023602 |
20 | 256738751 |
21 | 848152864 |
22 | 2811996972 |
23 | 9353366564 |
24 | 31204088381 |
25 | 104384620070 |
26 | 350064856815 |
27 | 1176693361956 |
28 | 3963752002320 |
[1] A.A. Jones, F. Protti and R.R. Del-Vecchio, Cograph generation with linear delay, Theoretical Computer Science, 713:1-10, 2018.