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

Updated Oct 8

Problem 799

claims/: The 2 claim pages of Problem 799, 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.

Is it true that $\chi_L(G)=o(n)$ for almost all graphs on $n$ vertices?

Status. Proved.

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

References.

[AKS99] Alon, Noga and Krivelevich, Michael and Sudakov, Benny, List coloring of random and pseudo-random graphs. Combinatorica (1999), 453-472.
[Al92] Alon, Noga, Choice numbers of graphs: a probabilistic approach. Combin. Probab. Comput. (1992), 107-114.

Formalization. The formal-conjectures project has no statement file for Problem 799; the $o(n)$ statement has a third-party Lean proof, linked from the claim page of Alon, Krivelevich and Sudakov below, which this corpus has not built.

Current assessment

The question, raised by Erdős, Rubin and Taylor, asks whether the list chromatic number of almost every graph on $n$ vertices is $o(n)$ , the graphs being counted uniformly, so that the statement concerns the random graph $G(n,1/2)$ almost surely. The answer is yes, twice over. Alon [Al92] proved $\chi_L(G(n,1/2))\ll n\log\log n/\log n$ almost surely; Alon, Krivelevich and Sudakov [AKS99] proved $\chi_L(G(n,p))\asymp np/\log(np)$ almost surely for $2<np\le n/2$ , which at $p=1/2$ is the order $n/\log n$ of the chromatic number itself. Each is an accepted full claim: Alon 1992 and Alon, Krivelevich and Sudakov 1999, both refereed journal papers credited by the site's curator. The second paper's introduction reports Kahn's asymptotic $\chi_L(G(n,1/2))=(1+o(1))n/(2\log_2 n)$ almost surely, with the argument described in Alon's survey Restricted colorings of graphs (Surveys in Combinatorics, 1993). That result is $o(n)$ and answers the question, but the corpus knows it only through that report and has not carded the survey, so it stays outside the derivation. No other claim appears on the site's forum or in the sources cited above.

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 (13)

Alon's bound on the choice number of random graphs Alon, Krivelevich and Sudakov's order of the choice number problems/graph_coloring/E0799/claims Graph Coloring graph_coloring/alon_1992_choice_numbers_graphs_probabilistic_approach Corollary 1.3 (p. 2): ch(G_{n,1/2}) <= c n log log n / log n almost surely Theorem 1.1 (p. 1): the choice number of K_{m*r} is of order r log m graph_coloring/alon_1999_list_coloring_random_pseudo_random_graphs Theorem 1.1 (p. 2): ch(G(n,p)) is of order np / ln(np) for 2 < np <= n/2 Theorem 1.2 (pp. 2-3): pseudo-random graphs have ch(G) <= 4np/(delta ln n)graph_coloring/erdos_1980_choosability_graphs Open problem (p. 152): the choice number of the random graph R_n is o(n) with probability tending to 1 Theorem (pp. 150--151): the random m x m bipartite graph has choice number between log m / log 6 and 3 log m / log 6

Graph