| Line 15: | Line 15: | ||
'''A basic example of how to use the theorems is a simple two-coloring of a square. <br>''' | '''A basic example of how to use the theorems is a simple two-coloring of a square. <br>''' | ||
| − | '''Step 1: Look at all the different possible combinations of colorings:''' | + | '''Step 1: Look at all the different possible combinations of colorings:''' |
| − | + | ||
| + | [[Image:TwoColoringCombinations.jpg]]<br> | ||
{| width="200" border="1" cellspacing="1" cellpadding="1" | {| width="200" border="1" cellspacing="1" cellpadding="1" | ||
|- | |- | ||
| − | | gggg | + | | gggg |
| − | | gggr | + | | gggr |
| − | | ggrg | + | | ggrg |
| rggg | | rggg | ||
|- | |- | ||
| − | | grgg | + | | grgg |
| − | | ggrr | + | | ggrr |
| − | | rgrg | + | | rgrg |
| rrgg | | rrgg | ||
|- | |- | ||
| − | | grrg | + | | grrg |
| − | | rgrr | + | | rgrr |
| − | | grrr | + | | grrr |
| rrgr | | rrgr | ||
|- | |- | ||
| − | | rrrg | + | | rrrg |
| − | | rrrr | + | | rrrr |
| − | | grrg | + | | grrg |
| rggr | | rggr | ||
|} | |} | ||
| − | + | <br> | |
== '''Definitions:''' == | == '''Definitions:''' == | ||
Revision as of 12:42, 20 April 2014
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?
Contents
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: Look at all the different possible combinations of colorings:
| gggg | gggr | ggrg | rggg |
| grgg | ggrr | rgrg | rrgg |
| grrg | rgrr | grrr | rrgr |
| rrrg | rrrr | grrg | rggr |
Definitions:
- Burnside
- Polya
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
