ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a bipartite graph with bipartition V=A⊔BV=A\sqcup B. Write ΔA\Delta_A and ΔB\Delta_B for the maximum degrees of vertices in AA and BB, respectively. The graph is (kA,kB)(k_A,k_B)-choosable if every list assignment giving vertices of AA lists of size kAk_A and vertices of BB lists of size kBk_B admits a proper coloring from the lists.

Alon–Cambie–Kang conjecture. Suppose that ΔA,ΔB≥2\Delta_A,\Delta_B\geq 2 and that kA,kBk_A,k_B are positive integers. Then:

  1. for every ε>0\varepsilon>0 there is a Δ0\Delta_0 such that GG is (kA,kB)(k_A,k_B)-choosable whenever kA≥ΔAεk_A\geq\Delta_A^\varepsilon, kB≥ΔBεk_B\geq\Delta_B^\varepsilon, and ΔA,ΔB≥Δ0\Delta_A,\Delta_B\geq\Delta_0;
  2. there is an absolute constant C>0C>0 such that GG is (kA,kB)(k_A,k_B)-choosable whenever kA≥Clog⁡ΔBk_A\geq C\log\Delta_B and kB≥Clog⁡ΔAk_B\geq C\log\Delta_A;
  3. there is an absolute constant C>0C>0 such that GG is (kA,kB)(k_A,k_B)-choosable whenever ΔA=ΔB=Δ\Delta_A=\Delta_B=\Delta and
kB≥C(Δlog⁡Δ)1/kAlog⁡Δ.k_B\geq C\left(\frac{\Delta}{\log\Delta}\right)^{1/k_A}\log\Delta.

These are asymmetric generalizations of the Alon–Krivelevich conjecture. The conjecture is stated for general bipartite graphs, while the source discusses corresponding results for complete bipartite graphs; its resolution status is not given.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.