Department of

Mathematics


Seminar Calendar
for events the week of Wednesday, August 21, 2019.

     .
events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
      July 2019             August 2019           September 2019   
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
     1  2  3  4  5  6                1  2  3    1  2  3  4  5  6  7
  7  8  9 10 11 12 13    4  5  6  7  8  9 10    8  9 10 11 12 13 14
 14 15 16 17 18 19 20   11 12 13 14 15 16 17   15 16 17 18 19 20 21
 21 22 23 24 25 26 27   18 19 20 21 22 23 24   22 23 24 25 26 27 28
 28 29 30 31            25 26 27 28 29 30 31   29 30               
                                                                   

Tuesday, August 20, 2019

2:00 pm in 343 Altgeld Hall,Tuesday, August 20, 2019

Refinements of Choice Number of Graphs

Xuding Zhu (Zheiang Normal University Math)

Abstract: In this talk, we discuss some refinements of choice number of graphs.
(1) We define a graph $G$ to be strongly fractional $r$-choosable if for any positive integer $m$, $G$ is $(\lceil rm \rceil, m)$-choosable, and define the strong fractional choice number $ch^∗_f(G)$ of $G$ to be the infimum $r$ for which G is strongly fractional $r$-choosable. The strong fractional choice number of a family $\mathcal G$ of graphs is defined to be the supremum of $ch^∗_f(G)$ for graph $G \in \mathcal G$. It is proved that the strong fractional choice number of planar graphs is at least $4+2/9$, and the strong fractional choice number of triangle free planar graphs is at least $3 + 1/17$.
(2) We say a graph $G$ is $(k + \epsilon)$-choosable if any subgraph $H$ of $G$ has a subset $X$ of vertices for which the following hold: (i) $|X| \le \epsilon|V (H)|$, (ii) for any list assignment $L$ of $G$ for which $|L(v)| = k+1$ for $v \in X$ and $|L(v)| = k$ for $v \in V (H)−X$, $H$ is $L$-colourable. It is proved that planar graphs are $(4 + 1/2)$-choosable and triangle free planar graphs are $(3 + 2/3)$-choosable.
(3) Assume $\lambda = (k_1, k_2, \dots, k_q)$ is a partition of an integer $k$. A $\lambda$-assignment of $G$ is a $k$-assignment $L$ of $G$ for which the colour set $\bigcup_{v \in V(G)} L(v)$ can be partitioned into $C_1 \cup C_2 \cup \dots \cup C_q$ such that $|L(v) \cap C_i| = k_i$ for every vertex $v$. We say $G$ is $\lambda$-choosable if $G$ is $L$-colourable for every $\lambda$-assignment $L$ of $G$. If $\lambda = \{k\}$, then $\lambda$-choosability is the same as $k$-choosability; if $\lambda = \{1,1,\dots,1\}$ then $\lambda$-choosability is the same as $k$-colourability. For other partitions $\lambda$ of $k$, $\lambda$-choosability form a complex hierachy of complexity of colourability. A recent result of Kermnitz and Voigt implies that for any partition $\lambda$ of $4$ other than $\{1,1,1,1\}$, there is a planar graph which is not $\lambda$-choosable (this is much stronger than the result that there are planar graphs that are not $4$-choosable). Some basic properties of $\lambda$-choosability and relation to some other colouring concepts will be discussed.