## You are here

Homechromatic polynomial

## Primary tabs

# chromatic polynomial

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)\neq 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 $|E|$=0, then trivially
$\chi(x)=x^{{|V|}}$ (where $|\cdot|$ 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

$\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 $|E|$, (1) shows that $\chi(G,x)$ is a polynomial over $\mathbb{Z}$.

By refining the argument a little, one can show

$\chi(x)=x^{{|V|}}-|E|x^{{|V|-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

$\chi(x)=\sum_{{F\subset E}}(-1)^{{|F|}}x^{{|V|-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)\neq 0$.

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

$t(x,y)=\sum_{{F\subset E}}(x-1)^{{r(E)-r(F)}}(y-1)^{{|F|-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.

## Mathematics Subject Classification

05C15*no label found*05B35

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia

new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz

Mar 26

new correction: Misspelled name by DavidSteinsaltz

Mar 21

new correction: underline-typo by Filipe

Mar 19

new correction: cocycle pro cocyle by pahio

Mar 7

new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier

new image: expected waiting time by robert_dodier

new image: plot W(t) = P(waiting time <= t) by robert_dodier