[Discrete-math-seminar] Wednesday, March 28 DAM Research Seminar: Hemanshu Kaul
Robert Ellis
rellis at math.iit.edu
Sat Mar 24 12:12:12 CST 2007
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.
More information about the Discrete-math-seminar
mailing list