login
A084268
Triangle read by rows: T(n,k) is the number of simple graphs on n unlabeled nodes having chromatic number k, 1 <= k <= n.
12
1, 1, 1, 1, 2, 1, 1, 6, 3, 1, 1, 12, 16, 4, 1, 1, 34, 84, 31, 5, 1, 1, 87, 579, 318, 52, 6, 1, 1, 302, 5721, 5366, 867, 81, 7, 1, 1, 1118, 87381, 155291, 28722, 2028, 118, 8, 1, 1, 5478, 2104349, 7855628, 1919895, 115391, 4251, 165, 9, 1, 1, 32302, 78315231, 675054876, 250530482, 14662562, 393963, 8214, 222, 10, 1
OFFSET
1,5
COMMENTS
T(n,1) = T(n,n) = 1 (here we count the empty graph and the complete graph). T(n,n-1) = n-1 (here we count the graphs with clique number equal to n-1). - Geoffrey Critzer, Oct 12 2016
Row sums give A000088. - Joerg Arndt, Oct 13 2016
LINKS
Keith Briggs, combinatorial graph theory, see entry "number of graphs on n nodes with clique number k".
FindStat - Combinatorial Statistic Finder, The chromatic number of a graph.
Eric Weisstein's World of Mathematics, Chromatic Number
Eric Weisstein's World of Mathematics, n-Chromatic Graph
EXAMPLE
Triangle begins:
1;
1, 1;
1, 2, 1;
1, 6, 3, 1;
1, 12, 16, 4, 1;
1, 34, 84, 31, 5, 1;
1, 87, 579, 318, 52, 6, 1;
1, 302, 5721, 5366, 867, 81, 7, 1;
1, 1118, 87381, 155291, 28722, 2028, 118, 8, 1;
1, 5478, 2104349, 7855628, 1919895, 115391, 4251, 165, 9, 1;
...
PROG
(Sage) # prints triangle with a leading zero in each row
for n in range(1, 8) :
st = [0 for j in range(n+1)]
G = graphs(n)
for g in G :
st[ g.chromatic_number() ] += 1
print(st)
# Joerg Arndt, Oct 13 2016
CROSSREFS
Partial row sums include A033995, A076315, A076316, A076317, A076318, A076319, A076320, A076321.
Row sums are A000088.
Cf. A084269 (connected), A115597 (essentially the same sequence).
Sequence in context: A156984 A181621 A307070 * A332405 A332403 A263341
KEYWORD
nonn,tabl
AUTHOR
Eric W. Weisstein, May 24 2003
EXTENSIONS
Offset corrected by Joerg Arndt, Oct 13 2016
a(36)-a(55) from Joerg Arndt, Oct 15 2016
a(56)-a(66) from Andrew Howroyd, Dec 02 2018
STATUS
approved