clarke@csri.toronto.edu (Jim Clarke) (11/24/88)
COMBINATORICS SEMINAR - Friday, December 2, 11:15 a.m. in RS 310
(RS = Rosebrugh Building, 8 Taddle Creek Road)
Lucien Haddad
Physical Sciences Division
University of Toronto
"Strong n-coloring of Relations"
An n-ary areflexive relation rho on a set A is a subset rho !subset A ** n
such that for every (x1, ..., xn) in rho and every 1 <= i < j <= n, xi != xj.
We assume that the areflexive relation rho has a certain symmetry and we study
the complexity of finding a strong n-coloring for rho, (a generalization of
the concept of graph coloring). In particular we find a polynomial reduction
from the H-coloring problem for graphs to the strong n-coloring problem for
relations.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke