Mon, 02 Jun 2008
17:00 -
18:00
L3
For any simple graph G and any positive integer lambda, let
P(G,lambda) denote the number of mappings f from V(G) to
{1,2,..,lambda} such that f(u) not= f(v) for every two adjacent
vertices u and v in G. It can be shown that
P(G,lambda) = \sum_{A \subseteq E} (-1)^{|A|} lambda^{c(A)}
where E is the edge set of G and c(A) is the number of components
of the spanning subgraph of G with edge set A. Hence P(G,lambda)
is really a polynomial of lambda. Many results on the chromatic
polynomial of a graph have been discovered since it was introduced
by Birkhoff in 1912. However, there are still many unsolved
problems and this talk will introduce the progress of some
problems and also some new problems proposed recently.
I shall review the construction and describe the upper bound proof, which illustrates how methods founded in algorithmic complexity can be applied to a discrete optimization problem that has puzzled some mathematicians and physicists for more than 150 years.