# Bipartite graphs with high list-chromatic numbers

In 1979, Erdös, Rubin and Taylor [2] introduced a beautiful new direction of graph colorings. We will say that a graph $$G$$ is $$k$$-choosable if for any assignment of a set ( or list") $$L_v$$ of $$k$$ colors to each vertex $$v$$ of $$G$$, it is possible to select a color $$\lambda_v \in L_v$$ for each $$v$$ so that $$\lambda_u \not = \lambda_v$$ if $$u$$ and $$v$$ are adjacent. The list chromatic number $$\chi_L(G)$$ is defined to be the least $$k$$ such that $$G$$ is $$k$$-choosable. Clearly, $$\chi_L(G) \geq \chi(G)$$ for any $$G$$ ( by taking $$L_v= \{1,2,\ldots,\chi(G)\}$$ for all $$v$$). However, the difference between $$\chi_L(G)$$ and $$\chi(G)$$ can be arbitrarily large. In general, $$\chi_L$$ can not be bounded in terms of $$\chi$$. In [2], the following was presented:

# Problem

Determine the smallest number $$n(k)$$ of vertices in a bipartite graph $$G$$ which is not $$k$$-choosable.

It was shown [2] that

$$\displaystyle 2^{k-1} < n(k) < k^2 2^{k+2}.$$

This was proved by relating $$n(k)$$ to the cardinality $$m(k)$$ of a smallest family of $$k$$-sets which does not have property $$B$$. (A family $${\mathcal F}$$ of sets has property B if there is a set $$S$$ which meets every set in $$\mathcal F$$, but contains no member of $$\mathcal F$$.) Namely, $$m(k) \leq n(k) \leq 2 m(k)$$ and $$m(k) < k^2 2^{k+1}$$. For small values, they showed $$n(2)=6=2m(2)$$ and conjectured $$n(3)=14$$, which was confirmed by Hanson, MacGillivray and Toft [4]

Erdös, Rubin and Taylor [2] characterized graphs with list chromatic number $$2$$. They proved that $$G$$ is $$2$$-choosable if and only if it is reducible to $$K_1$$, $$C_{2m+2}$$ or $$theta(2,2,2m)$$ by successive deletion of vertices of degree $$1$$, where $$theta(a,b,c)$$ is the graph consisting of three paths of lengths $$a$$,$$b$$ and $$c$$ with only endpoints in common. It was also shown that for almost all bipartite graphs with equal parts, there are constants $$c$$ and $$c'$$ such that the list chromatic number of $$G$$ is between $$c \log \vert V(G)\vert$$ and $$c' \log \vert V(G)\vert$$.

Thomassen [6] proved that planar graphs of girth $$5$$ are $$3$$-choosable and that, in fact, one may pre-color any $$5$$-cycle in the graph. In [2], it was conjectured that every planar graph is $$5$$-choosable and that $$5$$ is best possible. This conjecture was solved affirmatively by Thomassen [5] Voigt [7] gave a construction of a planar graph which is not $$4$$-choosable. A simpler construction of this was given by Gutner[3]

In [2], it was conjectured that every planar bipartite graph is $$3$$-choosable. This was proved in the affirmative by Alon and Tarsi. [1].

Bibliography
1 N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), 125-134.

2 P. Erdös, A. L. Rubin and H. Taylor, Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer. XXVI, 125-157, Utilitas Math., Winnipeg, Man., 1980.

3 S. Gutner, The complexity of planar graph choosability, Discrete Math. 159 (1996), 119-130.

4 D. Hanson, G. MacGillivray and B. Toft, Choosability of bipartite graphs, Ars Combin. 44 (1996), 183-192.

5 C. Thomassen,Every planar graph is $$5$$-choosable, J. Comb. Theory B 62 (1994), 180-181.

6 C. Thomassen, $$3$$-list-coloring planar graphs of girth $$5$$, J. Comb. Theory B 64 (1995), 101-107.

7 M. Voigt, List colourings of planar graphs, Discrete Math 120 (1993), 215-219.