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

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

Original entry on oeis.org

1, 1, 2, 5, 17, 81, 519, 5218, 81677, 2014360, 76140741, 4303246908

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, A076323, A076324, A076325, A076326, A076327, A076328.

Cf. A076279, A076315, A084269, A126737.

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

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

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

a(12) from Jinyuan Wang, Feb 23 2020

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

A363044 Triangle read by rows: T(n,k) is the number of unlabeled connected graphs with n nodes and packing chromatic number k, 1 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 4, 1, 0, 1, 9, 10, 1, 0, 1, 21, 61, 28, 1, 0, 1, 48, 305, 409, 89, 1, 0, 1, 109, 1475, 5077, 4097, 357, 1, 0, 1, 247, 6623, 55005, 129904, 67529, 1770, 1, 0, 1, 564, 28540, 505098, 3378636, 5792187, 1999810, 11734, 1

Offset: 1

Pontus von Brömssen, May 14 2023

The concept of the packing chromatic number was introduced by Goddard et al. (2008) under the name broadcast chromatic number. The term packing chromatic number was introduced by Brešar et al. (2007).

			Triangle begins:
  n\k| 1  2   3     4      5       6       7       8     9 10
  ---+-------------------------------------------------------
   1 | 1
   2 | 0  1
   3 | 0  1   1
   4 | 0  1   4     1
   5 | 0  1   9    10      1
   6 | 0  1  21    61     28       1
   7 | 0  1  48   305    409      89       1
   8 | 0  1 109  1475   5077    4097     357       1
   9 | 0  1 247  6623  55005  129904   67529    1770     1
  10 | 0  1 564 28540 505098 3378636 5792187 1999810 11734  1

Boštjan Brešar, Sandi Klavžar, and Douglas F. Rall, On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Applied Mathematics 155 (2007), 2303-2311.
Wayne Goddard, Sandra M. Hedetniemi, Stephen T. Hedetniemi, John M. Harris, and Douglas F. Rall, Broadcast chromatic numbers of graphs, Ars Combinatoria 86 (2008), 33-49.

Cf. A001349 (row sums), A084269 (chromatic number), A363043 (not necessarily connected).

T(n,1) = 0 for n >= 2. (The only connected graph with packing chromatic number 1 is the 1-node graph.)
T(n,2) = 1 for n >= 2. (The only connected graphs with packing chromatic number 2 are the star graphs on at least 2 nodes.)
T(n,n) = 1. (The only connected graph with n nodes and packing chromatic number n is the complete graph on n nodes.)

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

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 3, 1, 0, 3, 12, 5, 1, 0, 6, 50, 47, 8, 1, 0, 11, 230, 448, 152, 11, 1

Offset: 1

Peter Kagey, May 08 2023

All planar graphs have Hadwiger number <= 4. The converse is not true since planar graphs also disallow a minor of K_{3,3}. - Andrew Howroyd, Jun 18 2025

			Triangle begins:
1;
0,  1;
0,  1,   1;
0,  2,   3,   1;
0,  3,  12,   5,   1;
0,  6,  50,  47,   8,  1;
0, 11, 230, 448, 152, 11, 1;

Eric Weisstein's World of Mathematics, Hadwiger Number
Wikipedia, Hadwiger number

Row sums are A001349.
Column 2 is A000055 for n > 1.
Subdiagonal is A024206.
Cf. A084269.
Cf. A032766 (n-cocktail party graph). A353212 (n-path complement graph).

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

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

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

A363044 Triangle read by rows: T(n,k) is the number of unlabeled connected graphs with n nodes and packing chromatic number k, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs