Event Quick Finder

October 2012

S M T W T F S
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      

Events Search

Keyword

Type

Calendar of Events

Return to Calendar

Mathematics Program presents

The Coloring Graph and Variations

Thursday, October 18, 2012

[The Coloring Graph and Variations]
A lecture by
Ruth Haas
Smith College

A proper coloring is an assignment of a color to each vertex of a graph G so that neighboring vertices have different colors. Graph coloring has been a motivating topic for much of graph theory.

Suppose we change the color of just one vertex in a graph coloring. Can we get from one coloring to another by a sequence of vertex changes so that each step along the way is a proper coloring? The answer is of course yes, if we are allowed an unlimited number of colors.   What is the fewest colors we can have for this to work?

We introduce a new graph called the coloring graph to analyze this situation. The coloring graph, and similar constructions, can be used to solve problems ranging from counting the possible number of graph colorings to modeling spin configurations in atoms.

For more information, call 845-758-7362, or e-mail rose@bard.edu.

Time: 4:40 pm

Location: RKC 111