Transcription of THE CHROMATIC POLYNOMIAL
{{id}} {{{paragraph}}}
Example: marketing
THE CHROMATIC POLYNOMIAL
THE CHROMATIC POLYNOMIAL . CODY FOUTS. Abstract. It is shown how to compute the CHROMATIC POLYNOMIAL of a sim- ple graph utilizing bond lattices and the Mo bius Inversion Theorem, which requires the establishment of a refinement ordering on the bond lattice and an exploration of the Incidence Algebra on a partially ordered set. 1. Introduction A common problem in the study of graph Theory is coloring the vertices of a graph so that any two connected by a common edge are different colors. The vertices of the graph in Figure 1 have been colored in the desired manner. This is called a Proper Coloring of the graph . Frequently, we are concerned with determining the least number of colors with which we can achieve a proper coloring on a graph . Furthermore, we want to count the possible number of different proper colorings on a graph with a given number of colors. We can calculate each of these values by using a special function that is associated with each graph , called the CHROMATIC POLYNOMIAL .
the four new graphs we have and so on. The process terminates when all of the remaining graphs are null graphs. Because the Chromatic Function of a null graph is a polynomial (P N n (k) = kn), we see that the Chromatic Function of Gis equal to the sum of a large number of polynomials and must itself be a polynomial. We
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: