An Attempt To Classify Bipartite Graphs by Their Chromatic Polynomial
Loading...
Date
2008-07-14
Authors
HasnI, Roslan
Journal Title
Journal ISSN
Volume Title
Publisher
Universiti Sains Malaysia
Abstract
For the purpose of tackling the four-colour problem, Birkhoff (1912) introduced the chromatic
polynomial of a map, denoted by P(M, A), which is a number of proper A-colouring of a map M.
Whitney (1932), who established many fundamental results for it, later generalized the notion of
a chromatic polynomial to that of an arbitrary graph. In 1968, Read asked whether it is possible
2
to find a set of necessary and sufficient algebraic conditions for a polynomial to be the chromatic
polynomial of some graph. In particular, Read asked for a necessary and sufficient condition for
two graphs to be chromatically equivalent; that is, to have the same chromatic polynomial. In
1978, Chao and Whitehead defined a graph to be chromatically unique if no other graphs share
its chromatic polynomial. Since then many researchers have been studying chromatic uniqueness
and chromatic equivalence of graphs. The question on chromatic equivalence and uniqueness is
called the chromaticity problem of graphs. Very recently, Dong, Koh and Teo (2005) finished a
monograph on chromatic polynomials and chromaticity of graphs. Salzberg et al. (1985), Tomescu
(1987) , Peng (1991) and many other reseachers, did the study for chromaticity of complete bipartite
graphs. Dong, Koh and Teo proved in three papers around 1990 that every complete bipartite graph
K(p, q), where p ~ q ~ 2, is chromatically unique. Since then, the chromaticity of graphs obtained
from K(p,q) by removing a set of edges has been studied by several researchers. In 2000 and
2001, Dong, Koh, Teo, Little and Hendy made full use of the notion a(G, 3) of the number of
3-independent partitions of the vertex set of a graph G to produce many families of chromatically
unique bipartite graphs. In 2005, Roslan and Peng extend some of their main results further. The
aim of this project is to study the chromatically unique bipartite graphs with certain edges deleted
and in general, to enhance the study of families of chromatically unique graphs.