A076316 -id:A076316 - 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

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

Original entry on oeis.org

1, 2, 4, 11, 34, 155, 1037, 12257, 272513, 11885351, 1003932892

Offset: 1

Eric W. Weisstein, Oct 06 2002

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

Cf. A033995, A076281, A076315, A076316, A076318, A076319, A076320, A076321.

Cf. A215620 (numbers of apex graphs on n vertices).

a(n) = A076316(n) + A076281(n). - Andrew Howroyd, Dec 02 2018

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

A223887 Number of 4-colored labeled graphs on n vertices.

Original entry on oeis.org

1, 4, 28, 340, 7108, 254404, 15531268, 1613235460, 284556079108, 85107970698244, 43112647751430148, 36955277740855136260, 53562598422461559373828, 131186989945696839128432644, 542676256323680030599454982148

Offset: 0

Peter Bala, Apr 10 2013

A simple graph G is a k-colorable graph if it is possible to assign one of k' <= k colors to each vertex of G so that no two adjacent vertices receive the same color. Such an assignment of colors is called a coloring function for the graph.
A k-colored graph is a k-colorable graph together with its coloring function. This sequence gives the number of labeled 4-colored graphs on n vertices. An example is given below.
See A047863 for labeled 2-colored graphs on n vertices and A191371 for labeled 3-colored graphs on n vertices. See A076316 for labeled 4-colorable graphs on n vertices and A224068 for the count of labeled graphs colored using exactly 4 colors.

			a(2) = 28: There are two labeled 4-colorable graphs on 2 nodes, namely
A)  1    2  B)  1    2
    o    o      o----o
Using 4 colors there are 16 ways to color the graph of type A and 4*3 = 12 ways to color the graph of type B so that adjacent vertices do not share the same color. Thus there are in total 28 labeled 4-colored graphs on 2 vertices.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973.

Andrew Howroyd, Table of n, a(n) for n = 0..50
Steven R. Finch, Bipartite, k-colorable and k-colored graphs
Steven R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
Eric Weisstein's World of Mathematics, k-Colorable Graph

Column k=4 of A322280.

Equals 4 * A000686, A047863 (labeled 2-colored graphs), A076316, A191371 (labeled 3-colored graphs), A224068.

N=66;  x='x+O('x^N);
E=sum(n=0, N, x^n/(n!*2^binomial(n,2)) );
tgf=E^4;  v=concat(Vec(tgf));
v=vector(#v, n, v[n] * (n-1)! * 2^((n-1)*(n-2)/2) )
/* Joerg Arndt, Apr 10 2013 */

a(n) = sum {k = 0..n} binomial(n,k)*2^(k*(n-k))*b(k)*b(n-k), where b(n) := sum {k = 0..n} binomial(n,k)*2^(k*(n-k)).

Let E(x) = sum {n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is E(x)^4 = sum {n >= 0} a(n)*x^n/(n!*2^C(n,2)) = 1 + 4*x + 28*x^2/(2!*2) + 340*x^3/(3!*2^3) + .... In general, for k = 1, 2, ..., E(x)^k is a generating function for labeled k-colored graphs (see Stanley).

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

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

Original entry on oeis.org

1, 1, 2, 6, 20, 107, 801, 10227, 231228, 9708788, 743177051, 100580560531

Offset: 1

Eric W. Weisstein, Oct 06 2002

Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong, Obstructions for three-coloring graphs without induced paths on six vertices, arXiv preprint, arXiv:1504.06979 [math.CO], 2015-2018.
Eric Weisstein's World of Mathematics, n-Colorable Graph

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

Cf. A076280, A076316, A084269, A126738.

A076316 = Cases[Import["https://oeis.org/A076316/b076316.txt", "Table"], {, }][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
EulerInvTransform[A076316] (* Jean-François Alcover, Sep 25 2019, updated Mar 17 2020 *)

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

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

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

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

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A223887 Number of 4-colored labeled graphs on n vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica