ABSTRACT: The {\em list chromatic number} $\chi_{\ell}(G)$ of a hypergraph $G=(V,E)$ is the minimum integer $s$ such that for every assignment of a list $L_v$ of $s$ colors to each vertex $v$ of $G$, there is a vertex coloring of $G$ in which the color of each vertex is in its list and there are no monochromatic edges. Fifteen year ago, Alon showed that the list chromatic number of every graph with average degree $d$ is at least $(0.5-o(1))\log_2 d$. In this talk, we discuss two related results by Alon and the speaker on list coloring of uniform hypergraphs.
The first of them states that for $r\geq 3$, every $r$-uniform hypergraph in which at least half of the $(r-1)$-vertex subsets are contained in at least $d$ edges has list chromatic number at least $ \frac{\ln d}{(20r)^3}$. When $r$ is fixed, this is sharp up to a constant factor. In particular, $n$-vertex $r$-uniform hypergraphs may have average degree about $(n/r)^{r-2}$ and still be $2$-list-colorable.
The second result concerns {\em simple} hypergraphs, that is, the hypergraphs in which any two distinct edges have at most one vertex in common. It is proved that for every fixed $r$, all $r$-uniform hypergraphs with high average degree have ``high" list chromatic number. The result implies that for any finite set of points $X$ in the plane, and for any finite integer $s$, one can assign a list of $s$ distinct colors to each point of the plane so that any coloring of the plane that colors each point by a color from its list contains a monochromatic isometric copy of $X$. As mentioned above, this is joint work with Noga Alon.

ABSTRACT: In search of ways to attack Hadwiger's Conjecture, Woodall and independently Seymour suggested to prove the weaker conjecture that {\em Every $(s+t)$-chromatic graph has a $K_{s,t}$-minor.} If the conjecture were true for all values of $s$ and $t$, it would imply that for $k\geq 2$ every $(2k-2)$-chromatic graph has a $K_{k}$-minor. The conjecture is evident for $s=1$. The validity of the conjecture for $s=2$ and all $t$ was proved by Woodall, and also follows from a result by Chudnovsky, Reed, and Seymour. Prince and the speaker proved the conjecture for $s=3$ and $t\geq 6500$. Then the speaker proved the conjecture for arbitrary $s$ if $t\geq C^{s^2}$. The aim of the talk is to show a refinement by Prince and the speaker: {\em Let $s$ and $t$ be positive integers such that $t>t_1(s):= (100s\log_2 s)^4.$ Then every $(s+t)$-chromatic graph has a $K^*_{s,t}$-minor, where $K^*_{s,t}$ is obtained from $K_{s,t}$ by adding all edges between the vertices of the partite set of size $s$.} The result is sharp in the sense that for every $s,t\geq 3$, there are infinitely many $(s+t)$-critical graphs that do not have $K_{s,t+1}$-minors.