A076317 -id:A076317 - cp's OEIS frontend

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

Eric W. Weisstein, May 24 2003

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

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

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

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

# 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

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

A076315 Number of 3-colorable (i.e., chromatic number <= 3) simple graphs on n nodes.

Original entry on oeis.org

1, 2, 4, 10, 29, 119, 667, 6024, 88500, 2109828, 78347534, 4383817811, 362181166439

Offset: 1

Eric W. Weisstein, Oct 06 2002

Eric Weisstein's World of Mathematics, n-Colorable Graph

Cf. A033995, A076279, A076316, A076317, A076318, A076319, A076320, A076321.

a(n) = A033995(n) + A076279(n). - Andrew Howroyd, Dec 02 2018

a(10)-a(11) from Andrew Howroyd, Dec 02 2018
a(12) from Brendan McKay, Jan 19 2020
a(13) from Brendan McKay, Nov 08 2022

A076316 Number of 4-colorable (i.e., chromatic number <= 4) simple graphs on n nodes.

Original entry on oeis.org

1, 2, 4, 11, 33, 150, 985, 11390, 243791, 9965456, 753402410, 101344230844

Offset: 1

Eric W. Weisstein, Oct 06 2002

Eric Weisstein's World of Mathematics, n-Colorable Graph

Cf. A033995, A076280, A076315, A076317, A076318, A076319, A076320, A076321.

a(n) = A076315(n) + A076280(n). - Andrew Howroyd, Dec 02 2018

a(10)-a(11) from Andrew Howroyd, Dec 02 2018

a(12) from Sean A. Irvine, Apr 13 2025

A076318 Number of 6-colorable (i.e., chromatic number <= 6) simple graphs on n nodes.

Original entry on oeis.org

1, 2, 4, 11, 34, 156, 1043, 12338, 274541, 12000742, 1018595454

Offset: 1

Eric W. Weisstein, Oct 06 2002

Eric Weisstein's World of Mathematics, n-Colorable Graph

Cf. A033995, A076282, A076315, A076316, A076317, A076319, A076320, A076321.

a(n) = A076317(n) + A076282(n). - Andrew Howroyd, Dec 02 2018

a(10)-a(11) from Andrew Howroyd, Dec 02 2018

A076319 Number of 7-colorable (i.e., chromatic number <= 7) simple graphs on n nodes.

Original entry on oeis.org

1, 2, 4, 11, 34, 156, 1044, 12345, 274659, 12004993, 1018989417

Offset: 1

Eric W. Weisstein, Oct 06 2002

Eric Weisstein's World of Mathematics, n-Colorable Graph

Cf. A033995, A076283, A076315, A076316, A076317, A076318, A076320, A076321.

a(n) = A076318(n) + A076283(n). - Andrew Howroyd, Dec 02 2018

a(10)-a(11) from Andrew Howroyd, Dec 02 2018

A076320 Number of 8-colorable (i.e., chromatic number <= 8) simple graphs on n nodes.

Original entry on oeis.org

1, 2, 4, 11, 34, 156, 1044, 12346, 274667, 12005158, 1018997631

Offset: 1

Eric W. Weisstein, Oct 06 2002

Eric Weisstein's World of Mathematics, n-Colorable Graph

Cf. A033995, A076315, A076316, A076317, A076318, A076319, A076321, A205567.

a(n) = A076319(n) + A205567(n). - Andrew Howroyd, Dec 02 2018

a(10)-a(11) from Andrew Howroyd, Dec 02 2018

A076321 Number of 9-colorable (i.e., chromatic number <= 9) simple graphs on n nodes.

Original entry on oeis.org

1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005167, 1018997853

Offset: 1

Eric W. Weisstein, Oct 06 2002

Eric Weisstein's World of Mathematics, n-Colorable Graph

Cf. A033995, A076315, A076316, A076317, A076318, A076319, A076320, A205568.

Cf. A000088. [R. J. Mathar, Sep 21 2008]

a(n) = A076320(n) + A205568(n). - Andrew Howroyd, Dec 02 2018

a(10)-a(11) from Andrew Howroyd, Dec 02 2018

A076324 Number of connected 5-colorable (i.e., chromatic number <= 5) simple graphs on n nodes.

Original entry on oeis.org

1, 1, 2, 6, 21, 111, 847, 11036, 259022, 11599009, 991757695

Offset: 1

Eric W. Weisstein, Oct 06 2002

Eric Weisstein's World of Mathematics, k-Colorable Graph

Cf. A005142, A076322, A076323, A076325, A076326, A076327, A076328.

Cf. A076281, A076317, A084269, A126739.

Inverse Euler transform of A076317. - Andrew Howroyd, Dec 02 2018

a(10)-a(11) from Andrew Howroyd, Dec 02 2018

A215620 Numbers of apex graphs (graphs which become or remain planar upon the removal of a single vertex) on n vertices.

Original entry on oeis.org

1, 2, 4, 11, 34, 155, 1026, 11666, 226916, 6810525

Offset: 1

Eric W. Weisstein, Aug 17 2012

Trivially includes planar graphs.

Eric Weisstein's World of Mathematics, Apex Graph

Cf. A215621 (nonplanar apex graphs).

Cf. A076317 (number of 5-colorable simple graphs on n nodes).

a(10) from Eric W. Weisstein, Aug 20 2012

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

Extensions

A076315 Number of 3-colorable (i.e., chromatic number <= 3) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A076316 Number of 4-colorable (i.e., chromatic number <= 4) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A076318 Number of 6-colorable (i.e., chromatic number <= 6) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A076319 Number of 7-colorable (i.e., chromatic number <= 7) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A076320 Number of 8-colorable (i.e., chromatic number <= 8) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A076321 Number of 9-colorable (i.e., chromatic number <= 9) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A076324 Number of connected 5-colorable (i.e., chromatic number <= 5) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A215620 Numbers of apex graphs (graphs which become or remain planar upon the removal of a single vertex) on n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions