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.