Tuesday, December 13 2016
10:45 - 12:45

#### The notion of distinguishing colorings goes back to the seminalpaper of Albertson/Collins; a coloring of the vertices of a graph is saidto be Distinguishing if for every non-trivial automorphism $\phi$ of thegraph, there exists some vertex $v$ such that $v$ and $\phi(v)$ arecolored differently. There is a closely related (and newer) notion inwhich every vertex is endowed with a list of colors, and the stipulationon the coloring is that each vertex is colored only with a color from itslist, and the least size of the lists that admits a distinguishingcoloring, irrespective of the lists themselves, is called its ListDistinguishing number. In this talk, we shall look at two problems:Concerning the distinguishing chromatic number (the coloring is alsoproper) for random Cayley graphs on certain Abelian groups, and theproblem for List distinguishing the Kneser graphs.This is based on Joint work with Sajith P.

Download as iCalendar

Done