Skip to main content
`Ctrl`+`K`

# chromatic_polynomial

chromatic_polynomial(G)

  Returns the chromatic polynomial of `G`

  This function computes the chromatic polynomial via an iterative version of the deletion-contraction algorithm.

  The chromatic polynomial `X_G(x)` is a fundamental graph polynomial invariant in one variable. Evaluating `X_G(k)` for an natural number `k` enumerates the proper k-colorings of `G`.

  There are several equivalent definitions; here are three:

  Def 1 (explicit formula): For `G` an undirected graph, `c(G)` the number of connected components of `G`, `E` the edge set of `G`, and `G(S)` the spanning subgraph of `G` with edge set `S` [1]:

  \[X_G(x) = \sum_{S \subseteq E} (-1)^{|S|} x^{c(G(S))}\]

  Def 2 (interpolating polynomial): For `G` an undirected graph, `n(G)` the number of vertices of `G`, `k_0 = 0`, and `k_i` the number of distinct ways to color the vertices of `G` with `i` unique colors (for `i` a natural number at most `n(G)`), `X_G(x)` is the unique Lagrange interpolating polynomial of degree `n(G)` through the points `(0, k_0), (1, k_1), dots, (n(G), k_{n(G)})` [2].

  Def 3 (chromatic recurrence): For `G` an undirected graph, `G-e` the graph obtained from `G` by deleting edge `e`, `G/e` the graph obtained from `G` by contracting edge `e`, `n(G)` the number of vertices of `G`, and `e(G)` the number of edges of `G` [3]:

  \[\begin{split}X_G(x) = \begin{cases} x^{n(G)}, & \text{if $e(G)=0$} \\ X_{G-e}(x) - X_{G/e}(x), & \text{otherwise, for an arbitrary edge $e$} \end{cases}\end{split}\]

  This formulation is also known as the Fundamental Reduction Theorem [4].

  Parameters:
    G NetworkX graph
  Returns:
    instance of `sympy.core.add.Add`

      A Sympy expression representing the chromatic polynomial for `G`.

  Notes

  Interpretation of the coefficients is discussed in [5]. Several special cases are listed in [2].

  The chromatic polynomial is a specialization of the Tutte polynomial; in particular, `X_G(x) = T_G(x, 0)` [6].

  The chromatic polynomial may take negative arguments, though evaluations may not have chromatic interpretations. For instance, `X_G(-1)` enumerates the acyclic orientations of `G` [7].

  References

  [1]

  D. B. West, “Introduction to Graph Theory,” p. 222

  [2] (1,2)

  E. W. Weisstein “Chromatic Polynomial” MathWorld–A Wolfram Web Resource https://mathworld.wolfram.com/ChromaticPolynomial.html

  [3]

  D. B. West, “Introduction to Graph Theory,” p. 221

  [4]

  J. Zhang, J. Goodall, “An Introduction to Chromatic Polynomials” https://math.mit.edu/~apost/courses/18.204_2018/Julie_Zhang_paper.pdf

  [5]

  R. C. Read, “An Introduction to Chromatic Polynomials” Journal of Combinatorial Theory, 1968 https://math.berkeley.edu/~mrklug/ReadChromatic.pdf

  [6]

  W. T. Tutte, “Graph-polynomials” Advances in Applied Mathematics, 2004 https://www.sciencedirect.com/science/article/pii/S0196885803000411

  [7]

  R. P. Stanley, “Acyclic orientations of graphs” Discrete Mathematics, 2006 https://math.mit.edu/~rstan/pubs/pubfiles/18.pdf

  Examples

      >>> C = nx.cycle_graph(5)
      >>> nx.chromatic_polynomial(C)
      x**5 - 5*x**4 + 10*x**3 - 10*x**2 + 4*x

      >>> G = nx.complete_graph(4)
      >>> nx.chromatic_polynomial(G)
      x**4 - 6*x**3 + 11*x**2 - 6*x