[ugrads] Discrete Seminar on Friday, 10/12, 12:45pm, RE106

Hemanshu Kaul kaul at iit.edu
Thu Oct 4 15:49:13 CDT 2018

Hello all,

We have another alum, *Jeff Mudrock*, visiting us next week. He will give a
talk on a coloring problem in Graph Theory in the Discrete Applied Math
Seminar at *12:45pm, on Friday, October 12th, in RE106*. Jeff successfully
completed his PhD earlier this year and was awarded the Menger Award for
outstanding graduate student by the department.

Jeff is a very good speaker and he intends to make the ideas in his *talk
accessible to all students with basic knowledge of Graph Theory*. So I
encourage all such students to attend the seminar.

An important and widely applied problem in graphs is the conflict-free
allocation of limited resources. For example we want to assign frequencies
(a limited resource) to radio stations (the entities; each with its own
list of potential frequencies) so that close-by stations get different
frequencies so that there is no interference (the conflict relationship).
Such fundamental resource allocation problems are studied as *``list
coloring problems on graphs''*. Jeff's talk will be on the list coloring
problem on graphs represented as Cartesian products, an efficient way of
representing large graphs using smaller ones.


*Title: *List Coloring a Cartesian Product with a Complete Bipartite Factor

*Presenter: *Jeffrey Mudrock, College of Lake County

*Date: *October 12, 2018

*Time: *12:45pm-1:40pm

*Location: *RE 106

List coloring, a variation on the typical vertex coloring problem, was
introduced independently by Vizing and by Erdos, Rubin, and Taylor in the
1970’s.  In list coloring the vertices of a graph are each assigned a list
of colors, a so called list assignment. For a given list assignment, we
seek a proper coloring of the graph such that the color we use on each
vertex comes from the list associated with the vertex.  The list chromatic
number of a graph is the smallest integer k such that the graph has a
proper list-coloring for any list assignment that assigns lists of size k
to each vertex in the graph.

Our work is motivated by a classic result demonstrating that complete
bipartite graphs can have arbitrarily large list chromatic number (far from
their chromatic number of 2). Here we study the list chromatic number of
the Cartesian product of a graph with a complete bipartite graph and when
it is as large as possible, far from its chromatic number. We prove tight
bounds, improving previously known best results. We also present
interesting results in the case that *G* is strongly chromatic-choosable
which is a notion of criticality that was recently introduced by H. Kaul
and the presenter. Our main tool for obtaining results is the list color
function which is a list analogue of the chromatic polynomial. This is
joint work with Hemanshu Kaul.


I hope to see you there.


Hemanshu Kaul
Associate Professor of Applied Mathematics
Co-Director, Graduate Program on Decision Sciences (CDSOR)
Illinois Institute of Technology
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://math.iit.edu/pipermail/ugrads/attachments/20181004/00c37cfd/attachment.html>

More information about the ugrads mailing list