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).

graphOEIStheta(G_1), theta(G_2), ...
Andrásfai graphA2803331, 1, 12, 815, 157762, ...
antiprism graphA294152X, X, 11, 38, 112, 309, 828, 2190, 5759, ...
Apollonian networkA0000002, 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 graphA000000X, X, 2816, ...
empty graph K^__nA0000001, 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 graphA0000004, 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_nA0000001, 1, 1, 238, ...
odd graph O_nA0000001, 1, 36, ...
permutation star graph PS_nA0000001, 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 graphA0000002, 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 graphA0000001, 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 Web Resource. https://mathworld.wolfram.com/ChromaticInvariant.html

Subject classifications