Applied Mathematics’ Hemanshu Kaul and Alumnus Hong Liu Give Invited Talks at 2018 International Workshop on Graph Theory
Hemanshu Kaul, associate professor of applied mathematics, spoke at the 2018 International Workshop on Graph Theory at Ewha Women’s University, Seoul, South Korea, January 4–7. His talk was “Chromatic-choosable Cartesian Products of Graphs: Criticality and the List Color Function,” describing research he did with his Ph.D. student Jeffrey Mudrock.
Graphs are mathematical structures that model relationships such as friendship, genetic ancestry, weblinks, transportation links, etc., between all sorts of entities like humans, organisms, genomes, webpages, cities, and more. They are the mathematical structures underlying networks of all kinds including transportation, social, internet, or epidemiological networks.
An important and widely applied problem in graphs is the conflict-free allocation of limited resources. For example, let’s say you want to assign frequencies (a limited resource) to radio stations (the entities), with nearby stations getting different frequencies so that there is no interference (the conflict relationship). Such fundamental resource allocation problems are studied as “list coloring problems on graphs.”
Hemanshu and Murdock’s research studies the list coloring problem on graphs represented as Cartesian products, an efficient way of representing large graphs using smaller ones. They introduce new techniques and concepts to the study of this problem, including a new notion of criticality, and use of the list color function, which lead to new advances showing how this problem reduces to an easier coloring problem on certain large classes of graphs. These ideas should find applications in a wide variety of list coloring problems.
Another invited speaker was Hong Liu, who earned his M.S. in applied math at Illinois Tech in 2010 including a thesis under Michael Pelsmajer, associate professor of applied mathematics, and is currently a Leverhulme Early Career Fellow at the University of Warwick. Liu gave a talk on an exact solution to the Erdos-Rademacher problem, an important question dating back to 1941 about the coloring problem on the class of triangle-free graphs, and it was one of the highlights of the workshop, Kaul said.
