We discuss in class colorings of graphs, where adjacent vertices have different colors. Suppose you took the graph to be a polygon and allowed the graph to be reflected and rotated. How many different colorings do you get?

Outline/Title?

Introduction

In graph theory, it is sometimes necessary to find the number of ways to color the vertices of a polygon. Two theorems that work together to solve this problem are the Polya theorem and Burnside theorem. 

Example 1:  Square

A basic example of how to use the theorems is a simple two-coloring of a square.

Step 1: The six unique graphs are shown for a two-coloring of a 2x2 square:

Step 2: Finding the isomorphic graphs for each unique graph:

This provides a lists of all the different colorings possible.

Step 4: Applying the eight possible orbits to the various colorings:

Orbit: An orbit is a term to describe the group of actions that act upon a set elements. In this example the actions are the basic motions of rotating and reflecting along a set axis and the motion that it induces on the points.

Below are examples used for a square.

This gives the following chart:

Definitions: 

• Burnside-The lemma counts the number of orbits of a set X acted upon by a group G. # of Orbits = (1/|G|) Sum over G |x^g|. Where x^g is an element of x such that g(x) = x, and  |x^G| is the number of elements that fit this defintion.
• Polya-Applies this to colors.

'
'Formula:

• show formula
• breakdown of each element
• relate back to example 1

Proof:

References and Additional Information

For further reading on the Polya theorem:

http://arxiv.org/pdf/1001.0072.pdf

http://math.berkeley.edu/~mbaker/Tucker.pdf

http://www.whitman.edu/mathematics/SeniorProjectArchive/2012/Huisinga.pdf

Back to MA375 Spring 2014