A137568 Number of chromatically unique simple graphs on n nodes.

1, 2, 4, 7, 16, 41, 139, 704, 7270, 183606

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.
• Eric Weisstein's World of Mathematics, Simple Graph.

Crossrefs

Cf. A137567 (number of chromatically non-unique graphs).

Cf. A000088 (number of simple graphs).

Programs

Sage

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

Formula

a(n) = A000088(n) - A137567(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