A076322 -id:A076322 - cp's OEIS frontend

A084269 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes having chromatic number k, 1 <= k <= n.

1, 0, 1, 0, 1, 1, 0, 3, 2, 1, 0, 5, 12, 3, 1, 0, 17, 64, 26, 4, 1, 0, 44, 475, 282, 46, 5, 1, 0, 182, 5036, 5009, 809, 74, 6, 1, 0, 730, 80947, 149551, 27794, 1940, 110, 7, 1, 0, 4032, 2010328, 7694428, 1890221, 113272, 4125, 156, 8, 1, 0, 25598, 76115143, 667036310, 248580644, 14545025, 389583, 8040, 212, 9, 1

Offset: 0

Eric W. Weisstein, May 24 2003

			Triangle begins:
  1;
  0,   1;
  0,   1,     1;
  0,   3,     2,      1;
  0,   5,    12,      3,     1;
  0,  17,    64,     26,     4,    1;
  0,  44,   475,    282,    46,    5,   1;
  0, 182,  5036,   5009,   809,   74,   6, 1;
  0, 730, 80947, 149551, 27794, 1940, 110, 7, 1;
  ...

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

Row sums are A001349.
Columns k=3..7 are A126737, A126738, A126739, A126740, A241702.
Partial row sums include A005142, A076322, A076323, A076324, A076325, A076326, A076327, A076328.
Essentially the same table as A126736.
Cf. A084268 (not necessarily connected), A115597.

a(37)-a(66) 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

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

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

Original entry on oeis.org

1, 1, 2, 6, 21, 112, 852, 11110, 260962, 11712281, 1006302720

Offset: 1

Eric W. Weisstein, Oct 06 2002

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

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

Cf. A076282, A076318, A084269, A126740.

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

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

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

Original entry on oeis.org

1, 1, 2, 6, 21, 112, 853, 11116, 261072, 11716406, 1006692303

Offset: 1

Eric W. Weisstein, Oct 06 2002

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

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

Cf. A076283, A076319, A084269, A241702.

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

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

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

Original entry on oeis.org

1, 1, 2, 6, 21, 112, 853, 11117, 261079, 11716562, 1006700343

Offset: 1

Eric W. Weisstein, Oct 06 2002

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

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

Cf. A205567, A076320, A084269.

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

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

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

Original entry on oeis.org

1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716570, 1006700555

Offset: 1

Eric W. Weisstein, Oct 06 2002

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

Cf. A005142, A076322, A076323, A076324, A076325, A076326, A076327.
Cf. A205568, A076321, A084269.
Cf. A001349. [R. J. Mathar, Sep 21 2008]

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

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

A352208 Largest number of maximal 3-colorable node-induced subgraphs of an n-node graph.

Original entry on oeis.org

1, 1, 1, 4, 10, 20, 35, 56, 84

Offset: 1

Pontus von Brömssen, Mar 08 2022

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n).
In the following, FCB(n_1, ..., n_k) denotes the full cyclic braid graph with cluster sizes n_1, ..., n_k, as defined by Morrison and Scott (2017), i.e., the graph obtained by arranging complete graphs of orders n_1, ..., n_k (in that order) in a cycle, and joining all pairs of nodes in neighboring parts with edges.
  a(10) >= 140 by FCB(2, 2, 2, 2, 2);
  a(11) >= 268 by FCB(2, 2, 2, 2, 3);
  a(12) >= 517 by FCB(2, 2, 3, 2, 3);
  a(13) >= 911 by FCB(2, 3, 2, 3, 3);
  a(14) >= 1515 by FCB(2, 3, 3, 3, 3);
  a(15) >= 2525 by FCB(3, 3, 3, 3, 3).

			For 3 <= n <= 9, a(n) = binomial(n,3) = A000292(n-2) and the complete graph is optimal (it is the unique optimal graph for 4 <= n <= 9), but a(10) >= 140 > binomial(10,3).

Natasha Morrison and Alex Scott, Maximising the number of induced cycles in a graph, Journal of Combinatorial Theory Series B 126 (2017), 24-61.

Cf. A000292, A076315, A076322.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).

Limit_{n->oo} a(n)^(1/n) >= 911^(1/13) = 1.68909... .

cp's OEIS Frontend

A084269 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes having chromatic number k, 1 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

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

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A352208 Largest number of maximal 3-colorable node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula