Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 7

Problem 629

claims/: The 2 claim pages of Problem 629, one per claimant's result; the problem's standing derives from them.

Statement. The list chromatic number $\chi_L(G)$ is defined to be the minimal $k$ such that for any assignment of a list of $k$ colours to each vertex of $G$ (perhaps different lists for different vertices) a colouring of each vertex by a colour on its list can be chosen such that adjacent vertices receive distinct colours.

Determine the minimal number of vertices $n(k)$ of a bipartite graph $G$ such that $\chi_L(G)>k$ .

Status. Open.

Source. erdosproblems.com/629, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #629, https://www.erdosproblems.com/629.

References.

[ERT80] Erdős, Paul and Rubin, Arthur L. and Taylor, Herbert, Choosability in graphs. Congr. Numer. XXVI (1980), 125-157.
[HMT96] Hanson, Denis and MacGillivray, Gary and Toft, Bjarne, [[../library/graph_coloring/hanson_1996_choosability_bipartite_graphs/_index|Choosability of bipartite graphs]]. Ars Combin. 44 (1996), 183-192.
[RaSr00] Radhakrishnan, Jaikumar and Srinivasan, Aravind, Improved bounds and algorithms for hypergraph $2$ -coloring. Random Structures Algorithms (2000), 4-32.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (10)

Erdős, Rubin and Taylor's value n(2) = 6 Hanson, MacGillivray and Toft's value n(3) = 14 problems/graph_coloring/E0629/claims Graph Coloring graph_coloring/erdos_1980_choosability_graphs Theorem (p. 129): M_k <= N(2,k) <= 2M_k for the fewest nodes of a 2-colorable graph that is not k-choosable Theorem (A. L. Rubin, p. 132): a connected graph is 2-choosable exactly when its core is K_1, an even cycle or a theta graph Theta_{2,2,2m}graph_coloring/hanson_1996_choosability_bipartite_graphs graph_coloring/radhakrishnan_2000_improved_bounds_algorithms_hypergraph_coloring Theorem 2.1 (p. 7): every n-uniform hypergraph with at most (1/10) sqrt(n/ln n) 2^n edges, or 0.7 sqrt(n/ln n) 2^n edges for large n, is 2-colorable

Graph