Asymmetric list-colouring conjecture for bipartite graphs

Let G=(V=AB,E)G=(V=A\cup B,E) be a bipartite graph with maximum degrees on AA and BB at most ΔA\Delta_A and ΔB\Delta_B, respectively. For positive integers kAk_A and kBk_B, say that GG is (kA,kB)(k_A,k_B)-choosable if every assignment of lists of size kAk_A to vertices of AA and size kBk_B to vertices of BB admits a proper list colouring. Asymmetric list-colouring conjecture. Let the positive integers ΔA\Delta_A, ΔB\Delta_B, kAk_A, and kBk_B satisfy one of the following: given ε>0\varepsilon>0, ΔA,ΔBΔ0\Delta_A,\Delta_B\geq\Delta_0 for some Δ0=Δ0(ε)\Delta_0=\Delta_0(\varepsilon), with kAΔAεk_A\geq\Delta_A^\varepsilon and kBΔBεk_B\geq\Delta_B^\varepsilon; for some absolute constant C>1C>1, kAClogΔBk_A\geq C\log\Delta_B and kBClogΔAk_B\geq C\log\Delta_A; or ΔA=ΔB=Δ\Delta_A=\Delta_B=\Delta and, for some absolute constant C>0C>0, either kBC(Δ/logΔ)1/kAlogΔk_B\geq C(\Delta/\log\Delta)^{1/k_A}\log\Delta or kAC(Δ/logΔ)1/kBlogΔk_A\geq C(\Delta/\log\Delta)^{1/k_B}\log\Delta. Then every such graph GG is (kA,kB)(k_A,k_B)-choosable. The paper develops sufficient and necessary conditions for asymmetric list colouring and establishes several asymptotically sharp results, but this full conjecture remains open.

Sources & referencesView supporting material

Primary source

Noga Alon, Stijn Cambie and Ross J. Kang, “Asymmetric list sizes in bipartite graphs”, arXiv:2004.07457 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.