PlanetMath: chromatic polynomial

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (192)
Orphanage
Unclass'd
Unproven (496)
Corrections (20)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

chromatic polynomial

(Definition)

Let be a graph (in the sense of graph theory) whose set of vertices is finite and nonempty, and which has no loops or multiple edges. For any natural number , let $\chi(G,x)$ , or just $\chi(x)$ , denote the number of -colorations of , i.e. the number of mappings $f\colon V\to\{1,2,\ldots,x\}$ such that $f(a)\ne f(b)$ for any pair of adjacent vertices. Let us prove that $\chi$ (which is called the chromatic polynomial of the graph ) is a polynomial function in with coefficients in $\mathbb{Z}$ . Write for the set of edges in . 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 and construct two graphs having fewer edges than : is obtained from by contracting the edge , and is obtained from by omitting the edge . 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

which might or might not be valid for the edge

, 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

, where

is the number of connected components of

, 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

, and

denotes the rank of

, i.e. the number of elements of any maximal cycle-free subset of

. (Alternatively, the sum may be taken only over subsets

such that

is equal to the span of

; all other summands cancel out in pairs.)

The chromatic number of is the smallest 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 , 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)

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 MSC:	05C15 (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

forum policy

No messages.

Interact