Chromatic Polynomialls

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. rnIn 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 rnfor all graphs G = (V, E). rnThe 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.

Get Full Work

Report copyright infringement or plagiarism