Speaker: Claude Tardif, Royal Military College of Canada
Time:    Tuesday, October 22, 2:30 p.m.
Place:   room: SITE 5084, SITE building, University of Ottawa
Title:   Chromatic numbers of products of graphs.

Abstract: A ``product'' of two graphs G, H is a graph
whose vertex-set is the cartesian product of the
vertex-sets of G and H, where the edges in the product
are derived from the edges in the factors according to
some rules. Here are some examples of these rules:

	The categorical product GxH: The edges are the pairs
	(u,v)(u',v') such that uu' is an edge of G and vv'
	an edge of H.

	The cartesian product G[]H: The edges are the pairs
	(u,v)(u',v') such that u=u' and vv' is an edge of H,
	or v=v' and uu' is an edge of G.

	The lexicographic product G[H]: The edges are the pairs
	(u,v)(u',v') such that uu' is an edge of G, or u=u' and
	vv' is an edge of H.

Sometimes the knowledge of these products helps us to understand the
general behaviour of chromatic numbers; for instance, Catlin's
counterexample to Hajos' conjecture is the graph C_5[K_3].
On other occasions, the question of how the graph products
behave with respect to chromatic numbers give rise to deep problems;
for instance, nobody knows yet whether the chromatic number of
GxH is always equal to the minimum of the chromatic numbers of
G and H.

I will present both these aspects of graph products:
graph products as solutions and graph products as problems,
in a talk centered around ``chromatic difference sequences''
of graphs.