PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
chromatic polynomial (Definition)

Let $ G$ be a graph (in the sense of graph theory) whose set $ V$ of vertices is finite and nonempty, and which has no loops or multiple edges. For any natural number $ x$, let $ \chi(G,x)$, or just $ \chi(x)$, denote the number of $ x$-colorations of $ G$, i.e. the number of mappings $ f\colon V\to\{1,2,\ldots,x\}$ such that $ f(a)\ne f(b)$ for any pair $ (a,b)$ of adjacent vertices. Let us prove that $ \chi$ (which is called the chromatic polynomial of the graph $ G$) is a polynomial function in $ x$ with coefficients in $ \mathbb{Z}$. Write $ E$ for the set of edges in $ G$. If $ \vert E\vert$=0, then trivially $ \chi(x)=x^{\vert V\vert}$ (where $ \vert\cdot\vert$ denotes the number of elements of a finite set). If not, then we choose an edge $ e$ and construct two graphs having fewer edges than $ G$: $ H$ is obtained from $ G$ by contracting the edge $ e$, and $ K$ is obtained from $ G$ by omitting the edge $ e$. We have

$\displaystyle \chi(G,x)=\chi(K,x)-\chi(H,x)$ (1)

for all $ x\in\mathbb{N}$, because the polynomial $ \chi(K,x)$ is the number of colorations of the vertices of $ G$ which might or might not be valid for the edge $ e$, while $ \chi(H,x)$ is the number which are not valid. By induction on $ \vert E\vert$, (1) shows that $ \chi(G,x)$ is a polynomial over $ \mathbb{Z}$.

By refining the argument a little, one can show

$\displaystyle \chi(x)=x^{\vert V\vert}-\vert E\vert x^{\vert V\vert-1}+\ldots\pm sx^k\;,$
for some nonzero integer $ s$, where $ k$ is the number of connected components of $ G$, and the coefficients alternate in sign.

With the help of the Möbius-Rota inversion formula (see Moebius Inversion), or directly by induction, one can prove

$\displaystyle \chi(x)=\sum_{F\subset E}(-1)^{\vert F\vert}x^{\vert V\vert-r(F)}$
where the sum is over all subsets $ F$ of $ E$, and $ r(F)$ denotes the rank of $ F$ in $ G$, i.e. the number of elements of any maximal cycle-free subset of $ F$. (Alternatively, the sum may be taken only over subsets $ F$ such that $ F$ is equal to the span of $ F$; all other summands cancel out in pairs.)

The chromatic number of $ G$ is the smallest $ x>0$ such that $ \chi(G,x)>0$ or, equivalently, such that $ \chi(G,x)\ne0$.

The Tutte polynomial of a graph, or more generally of a matroid $ (E,r)$, is this function of two variables:

$\displaystyle t(x,y)=\sum_{F\subset E}(x-1)^{r(E)-r(F)}(y-1)^{\vert F\vert-r(F)}\;.$
Compared to the chromatic polynomial, the Tutte contains more information about the matroid. Still, two or more nonisomorphic matroids may have the same Tutte polynomial.



"chromatic polynomial" is owned by bbukh. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: matroid, chromatic number

Also defines:  Tutte polynomial
Keywords:  matroid, coloring
Log in to rate this entry.
(view current ratings)

Cross-references: variables, function, matroid, chromatic number, span, subsets, sum, Moebius inversion, connected components, integer, argument, induction, polynomial, finite set, coefficients, polynomial function, adjacent vertices, mappings, number, natural number, edges, multiple, loops, finite, vertices, graph theory, graph
There are 2 references to this entry.

This is version 5 of chromatic polynomial, born on 2003-09-29, modified 2003-10-19.
Object id is 4745, canonical name is ChromaticPolynomial.
Accessed 7242 times total.

Classification:
AMS MSC05C15 (Combinatorics :: Graph theory :: Coloring of graphs and hypergraphs)
 05B35 (Combinatorics :: Designs and configurations :: Matroids, geometric lattices)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)