A137567 Number of chromatically nonunique simple graphs on n nodes.

0, 0, 0, 4, 18, 115, 905, 11642, 267398, 11821562

Offset: 1

Author

Eric W. Weisstein, Jan 26 2008

Keywords

• nonn
• more
• hard

Links

• Eric Weisstein's World of Mathematics, Chromatic Polynomial.
• Eric Weisstein's World of Mathematics, Chromatically Unique Graph.

Crossrefs

Cf. A137568 (number of chromatically unique graphs).

Cf. A000088 (number of simple graphs).

Programs

Sage

def A137567(n):
    d = {}
    for g in graphs(n):
        c = g.chromatic_polynomial()
        d[c] = 1 if c not in d else d[c]+1
    return sum(d.values()) - d.values().count(1)  # D. S. McNeil, Jan 02 2011

Formula

a(n) = A000088(n) - A137568(n).

Extensions

a(9) from Eric W. Weisstein, Apr 07 2008

a(8) and a(9) corrected by Eric W. Weisstein, Jan 02 2011

a(10) from Eric W. Weisstein, Jun 09 2014