[Discrete-math-seminar] Wednesday, March 28 DAM Research Seminar: Hemanshu Kaul

[Robert Ellis]

Please join us for Wednesday's talk at 11am in E1 241.  Hemanshu Kaul will 
give a talk he is preparing for the ISMAA meeting March 30-31.

Wednesday, March 28
11am-noon 	E1 241 	Hemanshu Kaul (IIT Applied Mathematics)
Title: Breaking Symmetries in Graphs

We want to label vertices of a graph G in such a way that all symmetries 
of G are broken. Symmetries of a graph are established by its 
automorphisms, which identify vertices that are structurally 
indistinguishable. The distinguishing number of a graph G is the least 
number of (appropriately assigned) vertex-labels that destroy all 
label-preserving automorphisms of G (except the identity automorphism, of 
course). Next, we ask for vertex-labelings of a graph G that in addition 
to breaking its symmetries also give a proper coloring of G (i.e., 
adjacent vertices get different labels).  Distinguishing chromatic number 
of G is the least number of colors needed for a proper coloring of G with 
the property that the only color-preserving automorphism of G is the 
identity.

For both these concepts we are interested in situations that allow us to 
break symmetries without using too many extra labels (or colors). When are 
only two labels enough (for the distinguishing number)? The distinguishing 
chromatic number of G needs to be at least as large as the chromatic 
number of G (the least number of colors needed for a proper coloring of 
G). When can we get away with using just one color more than the chromatic 
number (for the distinguishing chromatic number)? In this talk, we will 
discuss how cartesian products of graphs give an answer for both these 
questions. All terminology will be defined and discussed during the talk.