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.

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

Author

Eric W. Weisstein, May 24 2003

Keywords

• nonn
• tabl

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

Examples

			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;
  ...
		

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

Crossrefs

Columns k=1..9 are A057427, A076278, A076279, A076280, A076281, A076282, A076283, A205567, A205568.

Partial row sums include A033995, A076315, A076316, A076317, A076318, A076319, A076320, A076321.

Row sums are A000088.

Cf. A084269 (connected), A115597 (essentially the same sequence).

Programs

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

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