TOPICS
Search

Chromatic Invariant

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The chromatic invariant theta(G) of a connected graph G is the number of spanning trees of G that have internal activity 1 and external activity 0.

For graphs other than the singleton graph (for which theta(K_1)=1), it is also given by

theta(G)=(-1)^n(dpi_G)/(dx)|_(x=1),

where n=V(G)=|G| is the vertex count and pi_G(x) is the chromatic polynomial of G.

A connected graph G is separable iff theta(G)=0 and is a series-parallel graph iff theta(G)<=1 (Biggs 1993, p. 109).

Unless otherwise stated, hydrogen atoms are usually ignored in the computation of such indices as organic chemists usually do when they write a benzene ring as a hexagon (Devillers and Balaban 1999, p. 25).

Special cases are summarized in the following table (Biggs 1993, p. 110). The index of each value list in the table starts at 1. An X indicates that the family in that row is not defined for the corresponding parameter value.

graphOEIStheta(G_1), theta(G_2), ...
Andrásfai graphA2803331, 1, 12, 815, 157762, ...
antiprism graphA294152X, X, 11, 38, 112, 309, 828, 2190, 5759, ...
Apollonian network2, 16, 8192, ...
n×n black bishop graphA2951701, 1, 0, 8, 3528, 18475776, ...
cocktail party graph K_(n×2)A2951662, 1, 11, 362, 21234, 1965624, 264398280, ...
complete bipartite graph K_(n,n)A0481441, 1, 5, 73, 2069, 95401, 6487445, 610093513, ...
complete tripartite graph K_(n,n,n)A1825531, 11, 1243, 490043, 463370491, ...
complete graph K_nA0001421, 1, 1, 2, 6, 24, 120, 720, 5040, 40320, ...
2n-crossed prism graphA295168X, 11, 85, 521, 2869, 15017, 76717, 387425, ...
crown graphA2951711, 11, 328, 16369, 1181276, ...
cube-connected cycle graphX, X, 2816, ...
empty graph K^__n1, 2, -3, 4, -5, 6, -7, 8, -9, 10, ...
Fibonacci cube graphA2959271, 0, 0, 1, 36, 58432, ...
folded cube graphA295172X, 1, 2, 73, 1872172, ...
gear graphA000027X, X, 2, 3, 4, 5, 6, 7, 8, 9 ...
grid graph P_n square P_nA1825171, 1, 3, 72, ...
grid graph P_n square P_n square P_nA2951731, 11, 156284551, ...
halved cube graphA295174X, 1, 1, 2, 362, 1784062800, ...
Hanoi graphA2951751, 64, 1073741824, ...
hypercube graph Q_nA2951761, 1, 11, 48253, ...
Keller graph4, 1872172, ...
n×n king graphA2951771, 2, 48, 31328, 473555616, ...
n×n knight graphA2951781, 4, -1, 78, 1306725, ...
Möbius ladder M_nA000325X, X, 5, 12, 27, 58, 121, 248, 503, 1014, ...
Mycielski graph M_n1, 1, 1, 238, ...
odd graph O_n1, 1, 36, ...
permutation star graph PS_n1, 1, 1, 87837, ...
prism graph Y_nA000295X, X, 4, 11, 26, 57, 120, 247, 502, 1013, ...
n×n queen graphA2951871, 2, 1308, 1238775828, ...
rook complement graph K_n square K_n^_A2951861, 0, 98, 787211620, ...
rook graph K_n square K_nA295184X, 1, 98, ...
Sierpiński gasket graphA2951891, 1, 27, 20346417, ...
Sierpiński tetrahedron graph2, 176, ...
sun graphA000142X, X, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, ...
torus grid graph C_n square C_nA295191X, X, 98, 48253, 121790284, ...
transposition graph1, 1, 5, ...
triangular graphA295192X, 1, 1, 11, 3444, 32396796, ...
triangular grid graphA2951901, 1, 1, 5, 97, 6739, 1611097, 1295101469, ...
triangular honeycomb obtuse knight graphA2951941, -3, 6, 0, 0, 11687, 100231463, ...
triangular honeycomb queen graphA2951951, 1, 11, 3714, 39103200, ...
wheel graph W_nA000027X, X, X, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
n×n white bishop graphA2952171, 1, 8, 2044, 18475776, ...

Closed forms are summarized in the following table, where L_n is a Lucas number, S(n,k) is a Stirling number of the second kind, and Gamma(z) is a gamma function.

graphchromatic invariant formula
antiprism graphL_(2n)-2n-1
complete bipartite graph K_(n,n)sum_(k=0)^(n-1)(k!)^2[S(n-1,k)]^2
complete graph K_n{1 for n=1; (n-2)! otherwise
complete tripartite graph K_(n,n,n)sum_(k=1)^(n)sum_(l=1)^(n)(-1)^(k+l+n)(1-k-l)^nGamma(k+l-1)S(n,k)S(n,l)
2n-crossed prism graph5^n-2^(n+1)(3n+1)
cycle graph C_n,1
empty graph K^__n{1 for n=1; (-1)^nn otherwise
gear graph2^n-n
helm graph0
ladder graph P_2 square P_n1
ladder rung graph nP_2{1 for n=1; 0 otherwise
Möbius ladder M_nn-1
pan graph0
path graph P_n{0 for n=1, 2; 1 otherwise
prism graph Y_n2^n-n-1
star graph S_n{1 for n=1, 2; 0 otherwise
sun graph(n-2)!
sunlet graphC_n circledot K_10
web graph0
wheel graph W_nn-2

See also

Chromatic Number, Chromatic Polynomial

Explore with Wolfram|Alpha

References

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 107-109, 1993.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, 1999.Sloane, N. J. A. Sequences A000027/M0472, A000142/M1675, A000295/M3416, A000325, and A048144 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Chromatic Invariant

Cite this as:

Weisstein, Eric W. "Chromatic Invariant." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ChromaticInvariant.html

Subject classifications