Department of

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

**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.