Department of Mathematics Colloquium
|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.