The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to study the four color problem. It was generalised to the Tutte polynomial by Hassler Whitney and W. T. Tutte, linking it to the Potts model of statistical physics.
George David Birkhoff introduced the chromatic polynomial in 1912, defining it only for planar graphs, in an attempt to prove the four color theorem. If denotes the number of proper colorings of G with k colors then one could establish the four color theorem by showing for all planar graphs G. In this way he hoped to apply the powerful tools of analysis and algebra for studying the roots of polynomials to the combinatorial coloring problem.
Hassler Whitney generalised Birkhoff’s polynomial from the planar case to general graphs in 1932. In 1968, Ronald C. Read 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.
For a graph G, counts the number of its (proper) vertex k-colorings.
Other commonly used notations include , , or .
There is a unique polynomial which evaluated at any integer k ≥ 0 coincides with ; it is called the chromatic polynomial of G.
For example, to color the path graph on 3 vertices with k colors, one may choose any of the k colors for the first vertex, any of the remaining colors for the second vertex, and lastly for the third vertex, any of the colors that are different from the second vertex's choice.
Therefore, is the number of k-colorings of .
For a variable x (not necessarily integer), we thus have .
(Colorings which differ only by permuting colors or by automorphisms of G are still counted as different.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
This course is an introduction to linear and discrete optimization.Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to p
This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and
This course covers the following topics: Introduction to conic optimization, Duality in conic programming, Sums of squares/ SemideFinite relaxation for independence number and chromatic number, Harmon
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 and contains information about how the graph is connected. It is denoted by . The importance of this polynomial stems from the information it contains about .
In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph. While graph drawing and graph representation are valid topics in graph theory, in order to focus only on the abstract structure of graphs, a graph property is defined to be a property preserved under all possible isomorphisms of a graph. In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph.
William Thomas Tutte OC FRS FRSC (tʌt; 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 major Nazi German cipher system which was used for top-secret communications within the Wehrmacht High Command. The high-level, strategic nature of the intelligence obtained from Tutte's crucial breakthrough, in the bulk decrypting of Lorenz-enciphered messages specifically, contributed greatly, and perhaps even decisively, to the defeat of Nazi Germany.
An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed p ...
EPFL2023
,
We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...
The vertex set of the Kneser graph K(n, k) is V = (([n])(k)) and two vertices are adjacent if the corresponding sets are disjoint. For any graph F, the largest size of a vertex set U subset of V such that K(n, k)[U] is F-free, was recently determined by Al ...