HOME

TheInfoList



OR:

The chromatic polynomial is a graph polynomial studied in
algebraic graph theory Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph th ...
, a branch of
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
. It counts the number of
graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
s as a function of the number of colors and was originally defined by
George David Birkhoff George David Birkhoff (March 21, 1884 – November 12, 1944) was an American mathematician best known for what is now called the ergodic theorem. Birkhoff was one of the most important leaders in American mathematics in his generation, and durin ...
to study the
four color problem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sha ...
. It was generalised to the
Tutte polynomial The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...
by
Hassler Whitney Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, characteristic classes, and geometric integration t ...
and
W. T. Tutte William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...
, linking it to the
Potts model In statistical mechanics, the Potts model, a generalization of the Ising model, is a model of interacting spins on a crystalline lattice. By studying the Potts model, one may gain insight into the behaviour of ferromagnets and certain other phenome ...
of
statistical physics Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the Mathematics, mathematical tools for dealing with large populations ...
.


History

George David Birkhoff George David Birkhoff (March 21, 1884 – November 12, 1944) was an American mathematician best known for what is now called the ergodic theorem. Birkhoff was one of the most important leaders in American mathematics in his generation, and durin ...
introduced the chromatic polynomial in 1912, defining it only for
planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
s, in an attempt to prove the
four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...
. If P(G, k) denotes the number of proper colorings of ''G'' with ''k'' colors then one could establish the four color theorem by showing P(G, 4)>0 for all planar graphs ''G''. In this way he hoped to apply the powerful tools of
analysis Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (38 ...
and
algebra Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics. Elementary a ...
for studying the roots of polynomials to the combinatorial coloring problem.
Hassler Whitney Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, characteristic classes, and geometric integration t ...
generalised Birkhoff’s polynomial from the planar case to general graphs in 1932. In 1968,
Ronald C. Read Ronald Cedric Read (19 December 1924 – 7 January 2019) was a British mathematician, latterly a professor emeritus of mathematics at the University of Waterloo, Canada. He published many books and papers, primarily on enumeration of Graph (discr ...
asked which polynomials are the chromatic polynomials of some graph, a question that remains open, and introduced the concept of chromatically equivalent graphs. Today, chromatic polynomials are one of the central objects of
algebraic graph theory Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph th ...
.


Definition

For a graph ''G'', P(G,k) counts the number of its (proper) vertex ''k''-colorings. Other commonly used notations include P_G(k), \chi_G(k), or \pi_G(k). There is a unique
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
P(G,x) which evaluated at any integer ''k'' ≥ 0 coincides with P(G,k); it is called the chromatic polynomial of ''G''. For example, to color the
path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
P_3 on 3 vertices with ''k'' colors, one may choose any of the ''k'' colors for the first vertex, any of the k - 1 remaining colors for the second vertex, and lastly for the third vertex, any of the k - 1 colors that are different from the second vertex's choice. Therefore, P(P_3,k) = k \cdot (k-1) \cdot (k-1) is the number of ''k''-colorings of P_3. For a variable ''x'' (not necessarily integer), we thus have P(P_3,x)=x(x-1)^2=x^3-2x^2+x. (Colorings which differ only by permuting colors or by
automorphisms In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...
of ''G'' are still counted as different.)


Deletion–contraction

The fact that the number of ''k''-colorings is a polynomial in ''k'' follows from a recurrence relation called the deletion–contraction recurrence or Fundamental Reduction Theorem. It is based on
edge contraction In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex ide ...
: for a pair of vertices u and v the graph G/uv is obtained by merging the two vertices and removing any edges between them. If u and v are adjacent in ''G'', let G-uv denote the graph obtained by removing the edge uv. Then the numbers of ''k''-colorings of these graphs satisfy: :P(G,k)=P(G-uv, k)- P(G/uv,k) Equivalently, if u and v are not adjacent in ''G'' and G+uv is the graph with the edge uv added, then :P(G,k)= P(G+uv, k) + P(G/uv,k) This follows from the observation that every ''k''-coloring of ''G'' either gives different colors to u and v, or the same colors. In the first case this gives a (proper) ''k''-coloring of G+uv, while in the second case it gives a coloring of G/uv. Conversely, every ''k''-coloring of ''G'' can be uniquely obtained from a ''k''-coloring of G+uv or G/uv (if u and v are not adjacent in ''G''). The chromatic polynomial can hence be recursively defined as :P(G,x)=x^n for the edgeless graph on ''n'' vertices, and :P(G,x)=P(G-uv, x)- P(G/uv,x) for a graph ''G'' with an edge uv (arbitrarily chosen). Since the number of ''k''-colorings of the edgeless graph is indeed k^n, it follows by induction on the number of edges that for all ''G'', the polynomial P(G,x) coincides with the number of ''k''-colorings at every integer point ''x'' = ''k''. In particular, the chromatic polynomial is the unique
interpolating polynomial In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset. Given a set of data points (x_0,y_0), \ldots, (x_n,y_n), with no ...
of degree at most ''n'' through the points :\left \.
Tutte William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...
’s curiosity about which other
graph invariant Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...
s satisfied such recurrences led him to discover a bivariate generalization of the chromatic polynomial, the
Tutte polynomial The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...
T_G(x,y).


Examples


Properties

For fixed ''G'' on ''n'' vertices, the chromatic polynomial P(G, x) is a monic polynomial of degree exactly ''n'', with integer coefficients. The chromatic polynomial includes at least as much information about the colorability of ''G'' as does the chromatic number. Indeed, the chromatic number is the smallest positive integer that is not a zero of the chromatic polynomial, : \chi (G)=\min\. The polynomial evaluated at -1, that is P(G,-1), yields (-1)^ times the number of
acyclic orientation In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orie ...
s of ''G''. The derivative evaluated at 1, P'(G, 1) equals the chromatic invariant \theta(G) up to sign. If ''G'' has ''n'' vertices and ''c''
components Circuit Component may refer to: •Are devices that perform functions when they are connected in a circuit.   In engineering, science, and technology Generic systems * System components, an entity with discrete structure, such as an assem ...
G_1, \ldots, G_c, then * The coefficients of x^0, \ldots, x^ are zeros. * The coefficients of x^c, \ldots, x^n are all non-zero and alternate in signs. * The coefficient of x^n is 1 (the polynomial is monic). * The coefficient of x^ is -, E(G), . We prove this via induction on the number of edges on a simple graph ''G'' with n vertices and k edges. When k = 0, ''G'' is an empty graph. Hence per definition P(G, x)= x^n. So the coefficient of x^ is 0, which implies the statement is true for an empty graph. When k = 1, as in ''G'' has just a single edge, P(G, x) = x^n - x^. Thus coefficient of x^ is -1 = -, E(G), . So the statement holds for k = 1. Using
strong induction Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ...  all hold. Informal metaphors help ...
assume the statement is true for k = 0,1,2,\ldots,(k-1). Let ''G'' have k edges. By the contraction-deletion principle,
P(G, x) = P(G-e, x) - P(G/e, x),
Let P(G-e, x) = x^n - a_x^ + a_x^-\cdots, and P(G/e, x) = x^ - b_ x^ + b_x^-\cdots.
Hence P(G, x) = x^n - (a_ +1)x^ +\cdots.
Since G-e is obtained from ''G'' by removal of just one edge ''e'', a_ = k - 1, so a_ + 1 = k and thus the statement is true for ''k''. * The coefficient of x^1 is (-1)^ times the number of acyclic orientations that have a unique sink, at a specified, arbitrarily chosen vertex. * The absolute values of coefficients of every chromatic polynomial form a log-concave sequence. * \scriptstyle P(G, x) = P(G_1, x)P(G_2,x) \cdots P(G_c,x) The last property is generalized by the fact that if ''G'' is a ''k''-clique-sum of G_1 and G_2 (i.e., a graph obtained by gluing the two at a clique on ''k'' vertices), then :P(G, x) = \frac. A graph ''G'' with ''n'' vertices is a tree if and only if :P(G, x) = x(x-1)^.


Chromatic equivalence

Two graphs are said to be ''chromatically equivalent'' if they have the same chromatic polynomial. Isomorphic graphs have the same chromatic polynomial, but non-isomorphic graphs can be chromatically equivalent. For example, all trees on ''n'' vertices have the same chromatic polynomial. In particular, (x-1)^3x is the chromatic polynomial of both the claw graph and the
path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
on 4 vertices. A graph is ''chromatically unique'' if it is determined by its chromatic polynomial, up to isomorphism. In other words, ''G'' is chromatically unique, then P(G, x) = P(H, x) would imply that ''G'' and ''H'' are isomorphic. All
cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
s are chromatically unique.


Chromatic roots

A
root In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the sur ...
(or ''zero'') of a chromatic polynomial, called a “chromatic root”, is a value ''x'' where P(G, x)=0. Chromatic roots have been very well studied, in fact, Birkhoff’s original motivation for defining the chromatic polynomial was to show that for planar graphs, P(G, x)>0 for ''x'' ≥ 4. This would have established the
four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...
. No graph can be 0-colored, so 0 is always a chromatic root. Only edgeless graphs can be 1-colored, so 1 is a chromatic root of every graph with at least one edge. On the other hand, except for these two points, no graph can have a chromatic root at a real number smaller than or equal to 32/27. A result of Tutte connects the
golden ratio In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0, where the Greek letter phi ( ...
\phi with the study of chromatic roots, showing that chromatic roots exist very close to \phi^2: If G_n is a planar triangulation of a sphere then :P(G_n,\phi^2) \leq \phi^. While the real line thus has large parts that contain no chromatic roots for any graph, every point in the
complex plane In mathematics, the complex plane is the plane formed by the complex numbers, with a Cartesian coordinate system such that the -axis, called the real axis, is formed by the real numbers, and the -axis, called the imaginary axis, is formed by the ...
is arbitrarily close to a chromatic root in the sense that there exists an infinite family of graphs whose chromatic roots are dense in the complex plane.


Colorings using all colors

For a graph ''G'' on ''n'' vertices, let e_k denote the number of colorings using exactly ''k'' colors ''up to renaming colors'' (so colorings that can be obtained from one another by permuting colors are counted as one; colorings obtained by
automorphisms In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...
of ''G'' are still counted separately). In other words, e_k counts the number of
partitions Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...
of the vertex set into ''k'' (non-empty) independent sets. Then k! \cdot e_k counts the number of colorings using exactly ''k'' colors (with distinguishable colors). For an integer ''x'', all ''x''-colorings of ''G'' can be uniquely obtained by choosing an integer ''k ≤ x'', choosing ''k'' colors to be used out of ''x'' available, and a coloring using exactly those ''k'' (distinguishable) colors. Therefore: : P(G,x) = \sum_^x \binom k! \cdot e_k = \sum_^x (x)_k \cdot e_k, where (x)_k = x(x-1)(x-2)\cdots(x-k+1) denotes the
falling factorial In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial :\begin (x)_n = x^\underline &= \overbrace^ \\ &= \prod_^n(x-k+1) = \prod_^(x-k) \,. \e ...
. Thus the numbers e_k are the coefficients of the polynomial P(G,x) in the basis 1,(x)_1,(x)_2,(x)_3,\ldots of falling factorials. Let a_k be the ''k''-th coefficient of P(G,x) in the standard basis 1,x,x^2,x^3,\ldots, that is: : P(G,x) = \sum_^n a_k x^k
Stirling number In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book ''Methodus differentialis'' (1730). They were rediscov ...
s give a
change of basis In mathematics, an ordered basis of a vector space of finite dimension allows representing uniquely any element of the vector space by a coordinate vector, which is a sequence of scalars called coordinates. If two different bases are considere ...
between the standard basis and the basis of falling factorials. This implies: :a_k = \sum_^ (-1)^ \beginj\\k\end e_j   and   e_k = \sum_^n \beginj\\k\end a_j.


Categorification

The chromatic polynomial is categorified by a homology theory closely related to Khovanov homology.


Algorithms

Computational problems associated with the chromatic polynomial include * finding the chromatic polynomial P(G, x) of a given graph ''G''; * evaluating P(G, x) at a fixed ''x'' for given ''G''. The first problem is more general because if we knew the coefficients of P(G, x) we could evaluate it at any point in polynomial time because the degree is ''n''. The difficulty of the second type of problem depends strongly on the value of ''x'' and has been intensively studied in
computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
. When ''x'' is a natural number, this problem is normally viewed as computing the number of ''x''-colorings of a given graph. For example, this includes the problem #3-coloring of counting the number of 3-colorings, a canonical problem in the study of complexity of counting, complete for the counting class #P.


Efficient algorithms

For some basic graph classes, closed formulas for the chromatic polynomial are known. For instance this is true for trees and cliques, as listed in the table above. Polynomial time algorithms are known for computing the chromatic polynomial for wider classes of graphs, including
chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cy ...
s and graphs of bounded
clique-width In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum num ...
. The latter class includes
cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...
s and graphs of bounded tree-width, such as
outerplanar graph In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two fo ...
s.


Deletion–contraction

The deletion-contraction recurrence gives a way of computing the chromatic polynomial, called the ''deletion–contraction algorithm''. In the first form (with a minus), the recurrence terminates in a collection of empty graphs. In the second form (with a plus), it terminates in a collection of complete graphs. This forms the basis of many algorithms for graph coloring. The ChromaticPolynomial function in the Combinatorica package of the computer algebra system
Mathematica Wolfram Mathematica is a software system with built-in libraries for several areas of technical computing that allow machine learning, statistics, symbolic computation, data manipulation, network analysis, time series analysis, NLP, optimizat ...
uses the second recurrence if the graph is dense, and the first recurrence if the graph is sparse. The worst case running time of either formula satisfies the same recurrence relation as the
Fibonacci numbers In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
, so in the worst case, the algorithm runs in time within a polynomial factor of :\phi^=\left (\frac \right)^\in O\left(1.62^\right), on a graph with ''n'' vertices and ''m'' edges. The analysis can be improved to within a polynomial factor of the number t(G) of spanning trees of the input graph. In practice,
branch and bound Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate soluti ...
strategies and
graph isomorphism In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) a ...
rejection are employed to avoid some recursive calls, the running time depends on the heuristic used to pick the vertex pair.


Cube method

There is a natural geometric perspective on graph colorings by observing that, as an assignment of natural numbers to each vertex, a graph coloring is a vector in the integer lattice. Since two vertices i and j being given the same color is equivalent to the i’th and j’th coordinate in the coloring vector being equal, each edge can be associated with a hyperplane of the form \. The collection of such hyperplanes for a given graph is called its graphic
arrangement In music, an arrangement is a musical adaptation of an existing composition. Differences from the original composition may include reharmonization, melodic paraphrasing, orchestration, or formal development. Arranging differs from orches ...
. The proper colorings of a graph are those lattice points which avoid forbidden hyperplanes. Restricting to a set of k colors, the lattice points are contained in the cube ,kn. In this context the chromatic polynomial counts the number of lattice points in the ,k/math>-cube that avoid the graphic arrangement.


Computational complexity

The problem of computing the number of 3-colorings of a given graph is a canonical example of a #P-complete problem, so the problem of computing the coefficients of the chromatic polynomial is #P-hard. Similarly, evaluating P(G, 3) for given ''G'' is #P-complete. On the other hand, for k=0,1,2 it is easy to compute P(G, k), so the corresponding problems are polynomial-time computable. For integers k>3 the problem is #P-hard, which is established similar to the case k=3. In fact, it is known that P(G, x) is #P-hard for all ''x'' (including negative integers and even all complex numbers) except for the three “easy points”. Thus, from the perspective of #P-hardness, the complexity of computing the chromatic polynomial is completely understood. In the expansion :P(G, x)= a_1 x + a_2x^2+\cdots +a_nx^n, the coefficient a_n is always equal to 1, and several other properties of the coefficients are known. This raises the question if some of the coefficients are easy to compute. However the computational problem of computing ''ar'' for a fixed ''r ≥ 1'' and a given graph ''G'' is #P-hard, even for bipartite planar graphs. No
approximation algorithms In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solut ...
for computing P(G, x) are known for any ''x'' except for the three easy points. At the integer points k=3,4,\ldots, the corresponding
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
of deciding if a given graph can be ''k''-colored is
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
. Such problems cannot be approximated to any multiplicative factor by a bounded-error probabilistic algorithm unless NP = RP, because any multiplicative approximation would distinguish the values 0 and 1, effectively solving the decision version in bounded-error probabilistic polynomial time. In particular, under the same assumption, this rules out the possibility of a fully polynomial time randomised approximation scheme (FPRAS). For other points, more complicated arguments are needed, and the question is the focus of active research. , it is known that there is no
FPRAS In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an insta ...
for computing P(G, x) for any ''x'' > 2, unless NP =  RP holds.


Notes


References

* * * * * * * * * * * * *. * * * * * * * *


External links

* *
PlanetMath PlanetMath is a free, collaborative, mathematics online encyclopedia. The emphasis is on rigour, openness, pedagogy, real-time content, interlinked content, and also community of about 24,000 people with various maths interests. Intended to be c ...
br>Chromatic polynomial
* Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle

{{DEFAULTSORT:Chromatic Polynomial Graph invariants Graph coloring