List Ramsey R_ℓ(K_{1,2}, k) parity gap

Open question on $R_\ell(K_{1,2}, k)$ for odd $k$ · arXiv:1902.07018

arXiv Informal medium confidence— first stated 2020-08-12

Authors: N. Alon, M. Bucić, T. Kalvari, E. Kuperwasser, T. Szabó

Status open high confidence

The question of whether $R_\ell(K_{1,2}, k) = k+1$ or $k+2$ for odd $k$ is equivalent to the List Colouring Conjecture for complete graphs of even order, asking whether $\chi'_\ell(K_n)$ equals $n-1 = \chi'(K_n)$ or $n$ for even $n$. The background result of H\"aggkvist and Janssen (1997) resolves the odd-$n$ case ($\chi'_\ell(K_n) = n$ for odd $n$), and Schauz (2010) settled the conjecture for $K_n$ when $n-1$ is prime, but the general even case remains open. No post-2020 paper resolving the full problem was found in the indexed literature.

Reviewer notes. The conjecture is closely related to the List Colouring Conjecture (also known as the List Edge Colouring Conjecture), which states that $\chi'_\ell(G) = \chi'(G)$ for every graph $G$. For complete graphs, the odd-order case is settled (H\"aggkvist-Janssen 1997: $\chi'_\ell(K_n) = n$ for odd $n$, matching $\chi'(K_n) = n$); the even-order case corresponds exactly to the open question in this paper. The Cambridge Core paper found (H\"aggkvist-Janssen, Combinatorics Probability and Computing, 1997) is the background result cited in the source paper, not a new resolution. The paper arXiv:2103.15175 (Multicolor list Ramsey numbers grow exponentially) by Conlon, Fox, He, Mubayi, Suk, Verstra\"ete (2021) addresses exponential growth of $R_\ell$ for non-$r$-partite hypergraphs but does not address $R_\ell(K_{1,2}, k)$ for odd $k$ specifically.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. We do not know whether $R_\ell(K_{1,2}, k)$ is $k + 1$ or $k + 2$ when $k$ is odd.

Context

For even $k$, the paper establishes $R_\ell(K_{1,2}, k) = k+1 = R(K_{1,2}, k)$ using the result of Häggkvist and Janssen that $\chi'_\ell(K_n) = \chi'(K_n)$ for odd $n$. The case of odd $k$ is equivalent to the List Colouring Conjecture for cliques of even order, which asks whether $\chi'_\ell(K_n)$ equals $n$ or $n-1$ for even $n$.

Notes. Stated in prose; directly tied to the open case of the List Colouring Conjecture for cliques of even order.

Source paper

List Ramsey numbers
N. Alon, M. Bucić, T. Kalvari, E. Kuperwasser, T. Szabó · 2020-08-12
https://arxiv.org/abs/1902.07018 PDF source