Alladi Ramakrishnan Hall

Distinguishing Random Cayley graphs and List distinguishing Kneser graphs randomly

Niranjan Balachandran

IIT Bombay

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