[ugrads] Discrete Seminar on Fri, 2/2 at 12:45pm
Hemanshu Kaul
kaul at iit.edu
Fri Jan 26 11:43:21 CST 2018
Dear Faculty and Students,
Please write back if you would like to be added to the Discrete Applied
Math seminar list. Our first talk of the semester is next Friday, 2/2, at
12:45pm in RE 106. See below for details.
Hemanshu
---------- Forwarded message ----------
From: Hemanshu Kaul <kaul at iit.edu>
Date: Fri, Jan 26, 2018 at 11:38 AM
Subject: Discrete Seminar on Fri, 2/2 at 12:45pm
To: discrete-math-seminar at math.iit.edu
Hello all,
We will have the first talk of the semester on *Friday, Feb 2nd at 12:45pm
in RE 106*. *Jeff Mudrock* will talk about *Proportional Choosability*, a
new notion of list coloring with equitable allocation of colors, that arose
out of questions and discussion after a talk by Jeff in this seminar last
year. The talk will be accessible to any one with a semester of graph
theory under their belts. See below for the abstract.
[Please mark your calendars also for a talk on Wednesday, Feb 7th at
12:45pm in RE106 by a visitor from UIUC (I will send details later).]
---------------------
*Proportional Choosability: A New List Analogue of Equitable Coloring*
*Jeff Mudrock, IIT*
*Date/Time/Location: Friday, 2/2/18, 12:45pm, RE 106. *
*Abstract*
The study of equitable coloring began with a conjecture of Erdos in 1964,
and it was formally introduced by Meyer in 1973. An equitable k-coloring
of a graph G is a proper k-coloring of G such that the sizes of the color
classes differ by at most one. In 2003 Kostochka, Pelsmajer, and West
introduced a list analogue of equitable coloring, called equitable
choosability. Specifically, given lists of available colors of size k at
each vertex of a graph G, a proper list coloring is equitable if each color
appears on at most ceiling(|V(G)|/k) vertices. Graph G is equitably
k-choosable if such a coloring exists whenever all the lists have size k.
In this talk we introduce a new list analogue of equitable coloring which
we call proportional choosability. For this new notion, the number of
times we use a color must be proportional to the number of lists in which
the color appears. Proportional k-choosability implies both equitable
k-choosability and equitable k-colorability, and the graph property of
being proportionally k-choosable is monotone. We will discuss proportional
choosability of graphs with small order, completely characterize
proportionally 2-choosable graphs, and illustrate some of the techniques we
have used to prove results. This is joint work with Hemanshu Kaul, Michael
Pelsmajer, and Benjamin Reiniger.
--------------------
Hope to see you there.
Hemanshu
Hemanshu Kaul
Associate Professor of Applied Mathematics
Co-Director, Graduate Program on Decision Sciences (CDSOR)
Illinois Institute of Technology
http://www.math.iit.edu/~kaul/
http://iit.edu/cdsor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://math.iit.edu/pipermail/ugrads/attachments/20180126/1f190a7b/attachment.html>
More information about the ugrads
mailing list