#### 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.

Done