|
| |
|
|
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.
|
|
28
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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, ...
|
|
|
MATHEMATICA
|
Reverse /@ CoefficientList[Table[ChromaticPolynomial[GridGraph[{n, n}], x], {n, 5}], x] // Flatten (* Eric W. Weisstein, May 01 2017 *)
|
|
|
CROSSREFS
|
Sums of absolute values of row elements give: A080690(n).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
