# [ugrads] PhD Defense Talk (& Discrete Seminar) on Friday, 3/23, 12pm, RE 034

Hemanshu Kaul kaul at iit.edu
Mon Mar 19 19:40:49 CDT 2018

Hello all,

You are all invited to a talk by *Jeff Mudrock* on *Friday, 3/23, 12pm, at
RE 034*. This talk constitutes the public portion of Jeff's PhD defense and
is open to all. Jeff will tell us about the research he has conducted as a
part of his PhD thesis on the list coloring problem and its equitable
variants.

See below for the detailed abstract.

Hemanshu

-----------------

*Title:  *On the list coloring problem and its equitable variants

*Speaker:  *Jeffrey Mudrock

*Date:  *March 23, 2018

*Time:  *12:00-1:00pm

*Location:  *RE 034

*Abstract*

List coloring was introduced independently by Vizing and Erdos, Rubin, and
Taylor in the 1970s.  Suppose we associate with each vertex, *v*, of a
graph a list, *L(v)*, of available colors.  A proper *L*-coloring of the
graph is a proper coloring such that the color used on each vertex, *v*,
comes from *L(v)*.  The list chromatic number of a graph *G* is the minimum
*k* such that there is a proper *L*-coloring of *G* whenever *L* assigns
lists of *k* colors to each vertex in *V(G)*.

The list chromatic number of the Cartesian product of graphs is not well
understood. The best result is by Borowiecki et al. (2006) who proved that
the list chromatic number of the Cartesian product of two graphs can be
bounded in terms of the list chromatic number and the coloring number of
the factors.  We use the Alon-Tarsi Theorem and an extension of it
discovered by Schauz (2010) to find improved bounds on the list chromatic
number and online list chromatic number of the Cartesian product of an odd
cycle or complete graph with a traceable graph.  We also generalize the
notion of strong critical graphs, introduced by Stiebitz et al. (2008), to
strong *k*-chromatic-choosable graphs, and we get a strictly larger family
of graphs that includes odd cycles, cliques, the join of a clique and any
strongly chromatic-choosable graph, and many more families of graphs. We
prove sharp bounds on the list chromatic number of certain Cartesian
products where one factor is a strong *k*-chromatic-choosable graph
satisfying an edge bound.  Our proofs rely on the notion of
unique-choosability as a sufficient condition for list colorability,
discovered by Akbari et al. (2006), and the list color function which is a
list version of the chromatic polynomial.
We also study list analogues of equitable coloring.  We begin by studying
equitable choosability which was introduced by Kostochka, Pelsmajer, and
West in 2003. Expounding upon a conjecture of Fu (1994) on total equitable
coloring, we form a conjecture regarding the equitable choosability of
total graphs, and we prove our conjecture for all graphs of maximum degree
at most 2.  Finally, we introduce a new list analogue of equitable
coloring: proportional choosability.  For this new notion, the number of
times a color is used must be proportional to the number of lists in which
the color appears. Proportional choosability has several useful and
surprising properties.  We study the proportional choosability of graphs
with small order and disconnected graphs, and we completely characterize
proportionally 2-choosable graphs.
--------------------------

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

On Mon, Feb 26, 2018 at 5:17 PM, Hemanshu Kaul <kaul at iit.edu> wrote:

> Hello all,
>
> Professor Alexandr Kostochka (UIUC) will give a colloquium talk on Monday,
> 3/5, at 1:50pm in RE 104. He will talk about the exciting new developments
> in the field of graph coloring through the topic of DP-coloring, a
> generalization of list coloring. Its a colloquium talk so most of it will
> be accessible to students. I strongly encourage all students to take
> advantage of this opportunity to hear one of the leading graph theorists in
> the world.
>
> You can find the abstract and other details at
> https://science.iit.edu/events/2018/mar/05/alexandr-kostochka
>
> I 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
>
>
> On Tue, Feb 20, 2018 at 1:03 PM, Hemanshu Kaul <kaul at iit.edu> wrote:
>
>> Hello all,
>>
>> This is just a reminder that we have a seminar tomorrow, * Wednesday,
>> 2/21, at 12:45pm in RE119*. We will have a visitor,* Xujun Liu*, from
>> UIUC, give a talk on packing chromatic number of cubic graphs. The talk
>> abstract is given below.
>>
>> I hope to see you there.
>>
>> Hemanshu
>>
>>
>> On Wed, Feb 14, 2018 at 3:21 PM, Hemanshu Kaul <kaul at iit.edu> wrote:
>>
>>> Hello all,
>>>
>>> Please mark your calendars for our next seminar on* Wednesday, 2/21, at
>>> 12:45pm in RE119*. We will have a visitor,* Xujun Liu*, from UIUC, give
>>> a talk on packing chromatic number of cubic graphs. The talk abstract is
>>> given below.
>>>
>>> Also note that we will have Professor Kostochka will be visiting us for
>>> a colloquium talk on Monday, March 5th at 1:50pm.
>>>
>>> I hope to see you at the talk.
>>> Hemanshu
>>>
>>> --------------------------
>>> *Title:* Packing chromatic number of cubic graphs
>>> *Speaker*: Xujun Liu, UIUC
>>> *Time/Location: *Wednesday, 2/21, at 12:45pm in RE119
>>> *Abstract: *A packing k-coloring of a graph G is a partition of the
>>> vertex set V(G) into sets V_1, ....,V_k, such that for each i, the distance
>>> between any two distinct x,y in V_i is at least i+1. The packing chromatic
>>> number of a graph G is the minimum k such that G has a packing k-coloring.
>>> Sloper showed that there are 4-regular graphs with arbitrarily large
>>> packing chromatic number. The question whether the packing chromatic number
>>> of subcubic graphs is bounded appears in several papers. We answer this
>>> question in the negative. Moreover, we show that for every fixed k and g >
>>> 2k+1, almost every n-vertex cubic graph of girth at least g has the packing
>>> chromatic number greater than k. Joint work with Jozsef Balogh and Alexandr
>>> Kostochka.
>>> ---------------------------
>>>
>>>
>>> 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
>>>
>>>
>>> On Tue, Feb 6, 2018 at 1:08 PM, Hemanshu Kaul <kaul at iit.edu> wrote:
>>>
>>>> Hello all,
>>>>
>>>> This is just a reminder that we have a visitor tomorrow, * Anton
>>>> Bernshteyn, from UIUC, giving a talk about a classic problem of coloring
>>>> triangle-free graphs, on Wednesday, 2/7, at 12:45pm in RE 106.* It
>>>> will include an exposition of some fundamental ideas in graph theory and
>>>> probability. particularly Lovasz Local Lemma.
>>>>
>>>> *Title*: *Upper bounds on the chromatic number for triangle-free
>>>> graphs*
>>>> *Speaker: Anton Bernshteyn, UIUC*
>>>> *Time/Location: *
>>>> * Wednesday, 2/7, at 12:45pm in RE 106*
>>>> *Abstract: *A classical theorem of Johansson from 1996 asserts that
>>>> $\chi(G)=O(\Delta/\ln\Delta)$ for triangle-free graphs $G$ of maximum
>>>> degree $\Delta$. Johansson's original proof of this result was quite
>>>> intricate and involved iterated applications of the Lov\'asz Local Lemma.
>>>> Recently, Molloy has sharpened Johansson's bound to
>>>> $\chi(G)\leq(1+o(1))\Delta/\ln\Delta$ using the so-called entropy
>>>> compression method---an algorithmic alternative to the Lov\'asz Local Lemma
>>>> developed by Moser and Tardos. In this talk, I will present a simple proof
>>>> of the Johansson--Molloy theorem that avoids the technicalities of the
>>>> entropy compression method and only uses the standard Local Lemma (albeit
>>>> in a somewhat nonstandard way). I will also talk about some extensions of
>>>> this result to more general notions of coloring, such as list and
>>>> DP-coloring.
>>>>
>>>> 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
>>>>
>>>>
>>>> On Thu, Feb 1, 2018 at 2:15 PM, Hemanshu Kaul <kaul at iit.edu> wrote:
>>>>
>>>>> Hello all,
>>>>>
>>>>> First, a reminder that we have a seminar tomorrow *(Friday, 2/2) at
>>>>> 12:45pm in RE 106. Jeff Mudrock, will talk about Proportional Choosability,
>>>>> *a form of equitable allocation of resources through list coloring.
>>>>> See the email below for the details including an abstract.
>>>>>
>>>>> Second, please note that we will have* Anton Bernshteyn, from UIUC,
>>>>> talk about a classic problem of coloring triangle-free graphs, on
>>>>> Wednesday, 2/7, at 12:45pm in RE 106.* It will include an exposition
>>>>> of some fundamental ideas in graph theory and probability. particularly
>>>>> Lovasz Local Lemma. Undergraduates who have not heard of Lovasz Local
>>>>> Lemma, stop by my office on Tuesday afternoon (after 1:30pm) and ask me. I
>>>>> strongly encourage you all to attend the seminar. Here is the abstract:
>>>>>
>>>>> *Title*: *Upper bounds on the chromatic number for triangle-free
>>>>> graphs*
>>>>> *Speaker: Anton Bernshteyn, UIUC*
>>>>> *Time/Location: *
>>>>> * Wednesday, 2/7, at 12:45pm in RE 106*
>>>>> *Abstract: *A classical theorem of Johansson from 1996 asserts that
>>>>> $\chi(G)=O(\Delta/\ln\Delta)$ for triangle-free graphs $G$ of maximum
>>>>> degree $\Delta$. Johansson's original proof of this result was quite
>>>>> intricate and involved iterated applications of the Lov\'asz Local Lemma.
>>>>> Recently, Molloy has sharpened Johansson's bound to
>>>>> $\chi(G)\leq(1+o(1))\Delta/\ln\Delta$ using the so-called entropy
>>>>> compression method---an algorithmic alternative to the Lov\'asz Local Lemma
>>>>> developed by Moser and Tardos. In this talk, I will present a simple proof
>>>>> of the Johansson--Molloy theorem that avoids the technicalities of the
>>>>> entropy compression method and only uses the standard Local Lemma (albeit
>>>>> in a somewhat nonstandard way). I will also talk about some extensions of
>>>>> this result to more general notions of coloring, such as list and
>>>>> DP-coloring.
>>>>>
>>>>>
>>>>> best regards,
>>>>> Hemanshu
>>>>>
>>>>>
>>>>> On Fri, Jan 26, 2018 at 11:38 AM, Hemanshu Kaul <kaul at iit.edu> wrote:
>>>>>
>>>>>> 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...