A076278 -id:A076278 - cp's OEIS frontend

A033995 Number of bipartite graphs with n nodes.

1, 1, 2, 3, 7, 13, 35, 88, 303, 1119, 5479, 32303, 251135, 2527712, 33985853, 611846940, 14864650924, 488222721992, 21712049275198, 1308300679611469, 106897965189674291, 11852113048215107822, 1784730721403509209215, 365323537513403184463273

Offset: 0

Ronald C. Read

All bipartite graphs are perfect. - Falk Hüffner, Nov 27 2015

EULER transform of A005142 [1, 1, 1, 3, 5, 17, ...] is [1, 2, 3, 7, 13, ...]. - Michael Somos, May 13 2019

			For n=1: o; n=2: o o, o-o; n=3: o o o, o o-o, o-o-o; n=4: o o o o, o o o-o, o-o o-o, o o-o-o, o-o-o-o, K_{2,2}, K_{3,1}. - _Michael Somos_, May 13 2019

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

Andrew Howroyd, Table of n, a(n) for n = 0..50
CombOS - Combinatorial Object Server, Generate graphs.
P. Erdős, D. J. Kleitman, and B. L. Rothschild, Asymptotic enumeration of k_n-free graphs. In Colloquio Internazionale sulle Teorie Combinatorie, (Rome, 1973), Tomo II, Atti dei Convegni Lincei, No. 17, pp. 19-27. Accad. Naz. Lincei, Rome.
P. Hanlon, The enumeration of bipartite graphs, Discrete Math. 28 (1979), 49-57.
S. Hougardy, Home Page.
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
Sage, Common Graphs (Graph Generators).
Eric Weisstein's World of Mathematics, Bipartite Graph.
Eric Weisstein's World of Mathematics, Bicolorable Graph.
Eric Weisstein's World of Mathematics, n-Colorable Graph.

Row sums of A297877.
The labeled version is A047864.
Equals A076278(n) + 1.
Cf. A005142 (connected).

A005142 = Cases[Import["https://oeis.org/A005142/b005142.txt", "Table"], {, }][[All, 2]];
(* EulerTransform is defined in A005195 *)
EulerTransform[Rest @ A005142] (* Jean-François Alcover, Mar 18 2020 *)

a(0)=1 prepended and terms a(21) and beyond from Andrew Howroyd, Sep 05 2018

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.

Original entry on oeis.org

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

A076279 Number of 3-chromatic (i.e., chromatic number equals 3) simple graphs on n nodes.

Original entry on oeis.org

0, 0, 1, 3, 16, 84, 579, 5721, 87381, 2104349, 78315231, 4383566676, 362178638727

Offset: 1

Eric W. Weisstein, Oct 06 2002

Keith M. Briggs, Combinatorial Graph Theory
Eric Weisstein's World of Mathematics, n-Chromatic Graph

Column k=3 of A084268.

Cf. A076278, A076280, A076281, A076282, A115597.

a(10) from Keith Briggs, Mar 14 2006
a(11) from Michael Sollami, Jan 28 2012
a(12)-a(13) from Brendan McKay, Nov 08 2022

A076281 Number of 5-chromatic (i.e., chromatic number equals 5) simple graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 1, 5, 52, 867, 28722, 1919895, 250530482

Offset: 1

Eric W. Weisstein, Oct 06 2002

Keith M. Briggs, Combinatorial Graph Theory
Eric Weisstein's World of Mathematics, n-Chromatic Graph

Column k=5 of A084268.

Cf. A076278, A076279, A076280, A076282.

a(10) from Keith Briggs, Mar 14 2006

a(11) from Michael Sollami, Jan 28 2012

A076280 Number of 4-chromatic (i.e., chromatic number equals 4) simple graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 1, 4, 31, 318, 5366, 155291, 7855628, 675054876

Offset: 1

Eric W. Weisstein, Oct 06 2002

Keith M. Briggs, Combinatorial Graph Theory
Eric Weisstein's World of Mathematics, n-Chromatic Graph

Column k=4 of A084268.

Cf. A076278, A076279, A076281, A076282.

a(10) from Keith Briggs, Feb 24 2006

a(11) from Michael Sollami, Jan 28 2012

A076282 Number of 6-chromatic (i.e., chromatic number equals 6) simple graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 6, 81, 2028, 115391, 14662562

Offset: 1

Eric W. Weisstein, Oct 06 2002

Keith M. Briggs, Combinatorial Graph Theory
Eric Weisstein's World of Mathematics, n-Chromatic Graph

Column k=6 of A084268.

Cf. A076278, A076279, A076280, A076281.

a(10) from Keith Briggs, Mar 14 2006

a(11) from Michael Sollami, Jan 28 2012

A115597 Triangle read by rows: let a(n,k) = number of graphs on n nodes with chromatic number k; T(n,k) = a(n,n-k), n >= 2, k=0..n-2.

Original entry on oeis.org

1, 1, 2, 1, 3, 6, 1, 4, 16, 12, 1, 5, 31, 84, 34, 1, 6, 52, 318, 579, 87, 1, 7, 81, 867, 5366, 5721, 302, 1, 8, 118, 2028, 28722, 155291, 87381, 1118, 1, 9, 165, 4251, 115391, 1919895, 7855628, 2104349, 5478

Offset: 2

N. J. A. Sloane, based on email from Keith Briggs, Mar 14 2006

			Table of values of a(n,k): number of graphs on n nodes with chromatic number k
n. = .1...2...3...4....5....6.....7......8........9.......10
k.----------------------------------------------------------
2....0...1...2...6...12...34....87....302.....1118.....5478... = A076278
3....0...0...1...3...16...84...579...5721....87381..2104349... = A076279
4....0...0...0...1....4...31...318...5366...155291..7855628... = A076280
5....0...0...0...0....1....5....52....867....28722..1919895... = A076281
6....0...0...0...0....0....1.....6.....81.....2028...115391... = A076282
7....0...0...0...0....0....0.....1......7......118.....4251
8....0...0...0...0....0....0.....0......1........8......165
9....0...0...0...0....0....0.....0......0........1........9
10...0...0...0...0....0....0.....0......0........0........1
Triangle begins:
1
1 2
1 3 6
1 4 16 12
1 5 31 84 34
1 6 52 318 579 87
1 7 81 867 5366 5721 302
1 8 118 2028 28722 155291 87381 1118
1 9 165 4251 115391 1919895 7855628 2104349 5478

Keith M. Briggs, Combinatorial Graph Theory

Cf. A076278, A076279, A076280, A076281, A076282.

Cf. A084268 (essentially the same sequence).

A076283 Number of 7-chromatic (i.e., chromatic number equals 7) simple graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 7, 118, 4251, 393963

Offset: 1

Eric W. Weisstein, Oct 06 2002

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

Column k=7 of A084268.

Cf. A076278, A076279, A076280, A076281, A076282.

a(10)-a(11) from Michael Sollami, Jan 28 2012

A205567 Number of 8-chromatic (i.e., chromatic number equals 8) simple graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 8, 165, 8214

Offset: 1

Michael Sollami, Jan 28 2012

Keith M. Briggs, Combinatorial Graph Theory
Eric Weisstein's World of Mathematics, n-Chromatic Graph

Column k=8 of A084268.

Cf. A076278, A076279, A076280, A076281.

A205568 Number of 9-chromatic (i.e., chromatic number equals 9) simple graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 9, 222

Offset: 1

Michael Sollami, Jan 28 2012

Keith M. Briggs, Combinatorial Graph Theory
Eric Weisstein's World of Mathematics, n-Chromatic Graph

Column k=9 of A084268.

Cf. A076278, A076279, A076281, A076282.

cp's OEIS Frontend

A033995 Number of bipartite graphs with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

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

A076279 Number of 3-chromatic (i.e., chromatic number equals 3) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Extensions

A076281 Number of 5-chromatic (i.e., chromatic number equals 5) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Extensions

A076280 Number of 4-chromatic (i.e., chromatic number equals 4) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Extensions

A076282 Number of 6-chromatic (i.e., chromatic number equals 6) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Extensions

A115597 Triangle read by rows: let a(n,k) = number of graphs on n nodes with chromatic number k; T(n,k) = a(n,n-k), n >= 2, k=0..n-2.

Views

Author

Keywords

Examples

Links

Crossrefs

A076283 Number of 7-chromatic (i.e., chromatic number equals 7) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Extensions

A205567 Number of 8-chromatic (i.e., chromatic number equals 8) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

A205568 Number of 9-chromatic (i.e., chromatic number equals 9) simple graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs