Newsgroups: ont.events
Path: utzoo!utgpu!jarvis.csri.toronto.edu!csri.toronto.edu!clarke
From: clarke@csri.toronto.edu (Jim Clarke)
Subject: U of Toronto combinatorics seminar, Dec. 2
Message-ID: <8811241637.AA12545@harbord.csri.toronto.edu>
Organization: University of Toronto, CSRI
Distribution: ont
Date: Thu, 24 Nov 88 11:37:02 EST


    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