Asymmetric list-colouring conjecture for bipartite graphs

About 6 years old · traced to

Let G=(V=A∪B,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, kA≥Clog⁡ΔBk_A\geq C\log\Delta_B and kB≥Clog⁡ΔAk_B\geq C\log\Delta_A; or ΔA=ΔB=Δ\Delta_A=\Delta_B=\Delta and, for some absolute constant C>0C>0, either kB≥C(Δ/log⁡Δ)1/kAlog⁡Δk_B\geq C(\Delta/\log\Delta)^{1/k_A}\log\Delta or kA≥C(Δ/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.

References

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.