Transcription of THE CHROMATIC POLYNOMIAL
{{id}} {{{paragraph}}}
Example: barber
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.
THE CHROMATIC POLYNOMIAL 3 Figure 4. C 4: A cycle graph on 4 vertices. Figure 5. P 3: A path graph on 3 vertices. A connected graph in which the degree of each vertex is 2 is a cycle graph. A cycle graph of nvertices is denoted by C
Loading..
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: