Discrete Applied Math Seminar By Christian Tomlins: Symmetry Breaking with Proper List Colorings

Speaker:

Christian Tomlins, Ph.D. candidate, Illinois Institute of Technology

Title:

Symmetry Breaking with Proper List Colorings

Abstract:

A coloring of a graph is said to be distinguishing if it breaks all color-preserving automorphisms, that is, no non-identity automorphism preserves every vertex color. In 1996, Albertson and Collins introduced the formal study of this notion by asking for the distinguishing number of a given graph G,  the least number of colors that guarantee such a distinguishing coloring for G. By restricting what kinds of colorings are considered, many different kinds of distinguishing numbers have been studied in the past 26 years. 

In this talk, we explore proper list-colorings of graphs that are also distinguishing and the corresponding choice-distinguishing number first studied by Ferrara et al. in 2013, who studied the choice-distinguishing number of Trees. We discuss some classes of graphs where the choice-distinguishing number is known exactly. We also show how the list color function, the chromatic polynomial analogue for list colorings, can be used in conjunction with the structure of the automorphism group of the graph to give an upper bound on the choice-distinguishing number of the Cartesian product of relatively prime graphs. 

 

The Discrete Applied Math seminar will be held most Fridays from 3:30 p.m. - 4:30 p.m. on Zoom during the Spring 2022 semester. Contact the seminar organizer for joining details.

 

Discrete Applied Math seminar