TOPICS
Search

Chromatic Invariant

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The chromatic invariant theta(G) of a finite connected simple graph G with at least two vertices is the number of spanning trees of G that have internal activity 1 and external activity 0 with respect to a fixed ordering of the edges. This count is independent of the ordering (Biggs 1993, pp. 107-108). For the singleton graph, theta(K_1)=1 is assigned separately.

For connected graphs other than the singleton graph, 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. The same formula defines an extension to disconnected graphs, for which the invariant can be negative.

A connected graph G with at least two vertices is separable iff theta(G)=0 (Biggs 1993, p. 109). A biconnected graph G with at least three vertices is a series-parallel graph iff theta(G)=1 (Oxley 1982, p. 269).

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. The index of each value list starts at 1, except for the white bishop graph row, which starts at 2. 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 graphA2951712, 0, 1, 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 graphA2951741, 1, 2, 362, 1784062800, ...
Hanoi graphA2951751, 1, 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_nA2951841, 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, 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 for parameters at which the graph families are defined 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_n1
empty graph K^__n{1 for n=1; (-1)^nn otherwise
gear graphn-1
helm graph0
ladder graph P_2 square P_n1
ladder rung graph nP_2{1 for n=1; 0 otherwise
Möbius ladder M_n2^n-n
pan graph0
path graph P_n{1 for n=1, 2; 0 otherwise
prism graph Y_n2^n-n-1
star graph S_n{1 for n=1, 2; 0 otherwise
sun graph(n-2)!
sunlet graph C_n circledot K_10
web graph0
wheel graph W_nn-2

The formulas for the complete graph, prism graph, and Möbius ladder are given by Biggs (1993, p. 110).

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-110, 1993.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, 1999.Oxley, J. G. "On Crapo's Beta Invariant for Matroids." Stud. Appl. Math. 66, 267-277, 1982. https://doi.org/10.1002/sapm1982663267.Sloane, N. J. A. Sequences A000027/M0472, A000142/M1675, A000295/M3416, A000325, A048144, A182517, A182553, A280333, A294152, A295166, A295168, A295170, A295171, A295172, A295173, A295174, A295175, A295176, A295177, A295178, A295184, A295186, A295187, A295189, A295190, A295191, A295192, A295194, A295195, A295217, and A295927 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