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,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

Table of n, a(n) for n=1..66.

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

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

Sequence in context: A156984 A181621 A307070 * A332405 A332403 A263341

Adjacent sequences: A084265 A084266 A084267 * A084269 A084270 A084271

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