Chromatic Polynomialls
No Thumbnail Available
Date
2011-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
The four-color theorem states that any planar graph G = (V, E) can be properly colored using at most four colors. The attempt to prove this famous mathematical problem gave rise to the development of many tools for solving problems related to graph coloring.
In 1912, Birkhoff introduced a function P(G,), define for all positive integer,to be the number of all proper colorings of a graph G = (V,E).This function turns out to be a polynomial in , and one could prove the four-color theorem by showing that P(G,) >0
for all graphs G = (V, E).
The polynomial P(G) is defined for all real and complex values of ,and it is called the chromatic polynomial of G = (V, E). In this project, we describe the properties of chromatic polynomials, discuss some practical methods for computing them, and look at the roots of chromatic polynomials .Classic results such as Whitney’s Broken-cycle theorem and Read’s Unimodal conjecture on the coefficients of P(G,) will also be discussed.
Description
Keywords
The four-color theorem states that any planar graph