Department of Mathematics Colloquium

University of Idaho

Fall 2012

Thursday,  November 1, 3:30-4:20 pm, room TLC 149

Refreshments in Brink 305 at 3:00 pm

Graph Embedding and Hedetniemi's Conjecture


Demitri Plessas

Department of Mathematical Sciences

University of Montana


In 1966 S. Hedetniemi conjectured that the chromatic number of the categorial product of two graphs with finite chromatic number would be the minimum of the chromatic number of the two graphs. In 1985 A. Hajnal found two graphs with an uncountable chromatic number that when taken together in the categorial product, produce a graph with a countable chromatic number. However Hedetniemi's conjecture remains open today.

In this talk, we will explore a portion of the results and techniques research into this conjecture has created as well as my own research into a new technique using the idea of graph embedding to provide a new special case of the conjecture.