A185442 -id:A185442 - cp's OEIS frontend

A182368 Triangle T(n,k), n>=1, 0<=k<=n^2, read by rows: row n gives the coefficients of the chromatic polynomial of the square grid graph G_(n,n), highest powers first.

1, 0, 1, -4, 6, -3, 0, 1, -12, 66, -216, 459, -648, 594, -323, 79, 0, 1, -24, 276, -2015, 10437, -40614, 122662, -292883, 557782, -848056, 1022204, -960627, 682349, -346274, 112275, -17493, 0, 1, -40, 780, -9864, 90798, -647352, 3714180, -17590911, 69997383

Offset: 1

Alois P. Heinz, Apr 26 2012

The square grid graph G_(n,n) has n^2 = A000290(n) vertices and 2*n*(n-1) = A046092(n-1) edges. The chromatic polynomial of G_(n,n) has n^2+1 = A002522(n) coefficients.

			3 example graphs:                          o---o---o
.                                          |   |   |
.                             o---o        o---o---o
.                             |   |        |   |   |
.                o            o---o        o---o---o
Graph:        G_(1,1)        G_(2,2)        G_(3,3)
Vertices:        1              4              9
Edges:           0              4             12
The square grid graph G_(2,2) is the cycle graph C_4 with chromatic polynomial q^4 -4*q^3 +6*q^2 -3*q => row 2 = [1, -4, 6, -3, 0].
Triangle T(n,k) begins:
  1,    0;
  1,   -4,     6,      -3,        0;
  1,  -12,    66,    -216,      459,       -648,         594, ...
  1,  -24,   276,   -2015,    10437,     -40614,      122662, ...
  1,  -40,   780,   -9864,    90798,    -647352,     3714180, ...
  1,  -60,  1770,  -34195,   486210,   -5421612,    49332660, ...
  1,  -84,  3486,  -95248,  1926585,  -30755376,   403410654, ...
  1, -112,  6216, -227871,  6205479, -133865298,  2382122274, ...
  1, -144, 10296, -487280, 17169852, -480376848, 11114098408, ...
  ...

Alois P. Heinz, Rows n = 1..9, flattened
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Grid Graph
Wikipedia, Chromatic Polynomial

Columns 0, 1 give: A000012, (-1)*A046092(n-1).
Sums of absolute values of row elements give: A080690(n).
Cf. A000290, A002522, A182406, A185442, A193233, A193277, A193283.

Reverse /@ CoefficientList[Table[ChromaticPolynomial[GridGraph[{n, n}], x], {n, 5}], x] // Flatten (* Eric W. Weisstein, May 01 2017 *)

A193277 Triangle T(n,k), n>=1, 0<=k<=(3+3^n)/2, read by rows: row n gives the coefficients of the chromatic polynomial of the Sierpinski gasket graph S_n, highest powers first.

Original entry on oeis.org

1, -3, 2, 0, 1, -9, 32, -56, 48, -16, 0, 1, -27, 339, -2625, 14016, -54647, 160663, -362460, 631828, -848736, 866640, -653248, 343744, -112896, 17408, 0, 1, -81, 3204, -82476, 1553454, -22823259, 272286183, -2711405961, 22990179324

Offset: 1

Alois P. Heinz, Jul 20 2011

The Sierpinski graph S_n has (3+3^n)/2 vertices and 3^n edges. The chromatic polynomial of S_n has (3+3^n)/2+1 coefficients.

			3 example graphs:                        o
.                                       / \
.                                      o---o
.                                     / \ / \
.                       o            o---o---o
.                      / \          / \     / \
.            o        o---o        o---o   o---o
.           / \      / \ / \      / \ / \ / \ / \
.          o---o    o---o---o    o---o---o---o---o
Graph:      S_1        S_2              S_3
Vertices:    3          6                15
Edges:       3          9                27
The Sierpinski graph S_1 is equal to the cycle graph C_3 with chromatic polynomial q^3 -3*q^2 +2*q => [1, -3, 2, 0].
Triangle T(n,k) begins:
1,    -3,       2,           0;
1,    -9,      32,         -56,           48,              -16,  ...
1,   -27,     339,       -2625,        14016,           -54647,  ...
1,   -81,    3204,      -82476,      1553454,        -22823259,  ...
1,  -243,   29295,    -2336013,    138604878,      -6526886841,  ...
1,  -729,  265032,   -64069056,  11585834028,   -1671710903793,  ...
1, -2187, 2389419, -1738877625, 948268049436, -413339609377179,  ...

Alois P. Heinz, Rows n = 1..7, flattened
Eric Weisstein's World of Mathematics, Chromatic Polynomial.
Eric Weisstein's World of Mathematics, Sierpiński Gasket Graph.
Wikipedia, Chromatic Polynomial.

Cf. A000244, A067771, A185442, A193233.

A212084 Triangle T(n,k), n>=0, 0<=k<=2n, read by rows: row n gives the coefficients of the chromatic polynomial of the complete bipartite graph K_(n,n), highest powers first.

Original entry on oeis.org

1, 1, -1, 0, 1, -4, 6, -3, 0, 1, -9, 36, -75, 78, -31, 0, 1, -16, 120, -524, 1400, -2236, 1930, -675, 0, 1, -25, 300, -2200, 10650, -34730, 75170, -102545, 78610, -25231, 0, 1, -36, 630, -6915, 52080, -279142, 1074822, -2942445, 5552680, -6796926, 4787174

Offset: 0

Alois P. Heinz, Apr 30 2012

The complete bipartite graph K_(n,n) has 2n vertices and n^2 = A000290(n) edges. The chromatic polynomial of K_(n,n) has 2n+1 = A005408(n) coefficients.

			3 example graphs:                     +-----------+
.                 o        o   o      o   o   o   |
.                 |        |\ /|      |\ /|\ /|\ /
.                 |        | X |      | X | X | X
.                 |        |/ \|      |/ \|/ \|/ \
.                 o        o   o      o   o   o   |
.                                     +-----------+
Graph:         K_(1,1)    K_(2,2)      K_(3,3)
Vertices:         2          4            6
Edges:            1          4            9
The complete bipartite graph K_(2,2) is the cycle graph C_4 with chromatic polynomial q^4 -4*q^3 +6*q^2 -3*q => row 2 = [1, -4, 6, -3, 0].
Triangle T(n,k) begins:
  1;
  1,  -1,   0;
  1,  -4,   6,    -3,     0;
  1,  -9,  36,   -75,    78,     -31,       0;
  1, -16, 120,  -524,  1400,   -2236,    1930,     -675, ...
  1, -25, 300, -2200, 10650,  -34730,   75170,  -102545, ...
  1, -36, 630, -6915, 52080, -279142, 1074822, -2942445, ...
  ...

Alois P. Heinz, Rows n = 0..90, flattened
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Wikipedia, Chromatic Polynomial

Columns k=0-2 give: A000012, (-1)*A000290, A083374.
Row sums and last elements of rows give: A000007.
Row lengths give: A005408.
Sums of absolute values of row elements give: A048163(n+1).
T(n,2n-1) = (-1)*A092552(n).
Cf. A008277, A212085, A182368, A185442, A193233, A193277, A193283, A266695, A266972.

P:= n-> add(Stirling2(n, k) *mul(q-i, i=0..k-1) *(q-k)^n, k=0..n):
T:= n-> seq(coeff(P(n), q, 2*n-k), k=0..2*n):
seq(T(n), n=1..8);

T(n,k) = [q^(2n-k)] Sum_{j=0..n} (q-j)^n * S2(n,j) * Product_{i=0..j-1} (q-i).

T(0,0)=1 prepended by Alois P. Heinz, May 03 2024

A193283 Triangle T(n,k), n>=1, 0<=k<=n*(n+1)/2, read by rows: row n gives the coefficients of the chromatic polynomial of the n X n X n triangular grid, highest powers first.

Original entry on oeis.org

1, 0, 1, -3, 2, 0, 1, -9, 32, -56, 48, -16, 0, 1, -18, 144, -672, 2016, -4031, 5368, -4584, 2272, -496, 0, 1, -30, 419, -3612, 21477, -93207, 304555, -761340, 1463473, -2152758, 2385118, -1929184, 1075936, -369824, 58976, 0

Offset: 1

Alois P. Heinz, Jul 20 2011

The n X n X n triangular grid has n rows with i vertices in row i. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has A000217(n) vertices and 3*A000217(n-1) edges altogether.

			4 example graphs:                           o
                                           / \
                              o           o---o
                             / \         / \ / \
                    o       o---o       o---o---o
                   / \     / \ / \     / \ / \ / \
              o   o---o   o---o---o   o---o---o---o
  n:          1     2         3             4
  Vertices:   1     3         6            10
  Edges:      0     3         9            18
The 2 X 2 X 2 triangular grid is equal to the cycle graph C_3 with chromatic polynomial q^3 -3*q^2 +2*q => [1, -3, 2, 0].
Triangle T(n,k) begins:
  1,   0;
  1,  -3,   2,      0;
  1,  -9,  32,    -56,     48,     -16,       0;
  1, -18, 144,   -672,   2016,   -4031,    5368, ...
  1, -30, 419,  -3612,  21477,  -93207,  304555, ...
  1, -45, 965, -13115, 126720, -925528, 5303300, ...
  ...

Alois P. Heinz, Rows n = 1..13, flattened
Wikipedia, Chromatic Polynomial
Wikipedia, Triangular grid graph

Cf. A000217, A045943, A178435, A182797, A185442, A193233, A193277.

cp's OEIS Frontend

A182368 Triangle T(n,k), n>=1, 0<=k<=n^2, read by rows: row n gives the coefficients of the chromatic polynomial of the square grid graph G_(n,n), highest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A193277 Triangle T(n,k), n>=1, 0<=k<=(3+3^n)/2, read by rows: row n gives the coefficients of the chromatic polynomial of the Sierpinski gasket graph S_n, highest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A212084 Triangle T(n,k), n>=0, 0<=k<=2n, read by rows: row n gives the coefficients of the chromatic polynomial of the complete bipartite graph K_(n,n), highest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A193283 Triangle T(n,k), n>=1, 0<=k<=n*(n+1)/2, read by rows: row n gives the coefficients of the chromatic polynomial of the n X n X n triangular grid, highest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs