# Bipartite graphs with high list-chromatic numbers

Search

Subjects

- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)

About Erdös

About This Site

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

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