← All problems

Jiang–Zhu relaxed multiplication question

For every pair of positive integers k,mk,m and every graph GG, if GG is kk-choosable— that is, every list assignment LL with ∣L(v)∣=k|L(v)|=k for all vertices vv admits a proper coloring cc with c(v)∈L(v)c(v)\in L(v)—then GG is (km+1:m)(km+1:m)-choosable— that is, every list assignment LL with ∣L(v)∣=km+1|L(v)|=km+1 for all vertices admits subsets S(v)⊆L(v)S(v)\subseteq L(v) with ∣S(v)∣=m|S(v)|=m such that S(u)∩S(v)=∅S(u)\cap S(v)=\varnothing whenever uv∈E(G)uv\in E(G)—.

Equivalent formulations
  1. For every graph GG, the strong fractional choice number of GG is at most its choice number.

    source: Counterexamples to Relaxed Multiplication in List Coloring

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

A November 2026 preprint claims to disprove the proposed list-coloring multiplication rule with an explicit small counterexample, but the claim has not been independently checked.

The question asks whether kk-choosability implies (km+1:m)(km+1:m)-choosability, equivalently whether the corresponding strong fractional choice-number bound always holds. Jiang and Zhu established important bounds for triangle-free planar graphs, while Dvořák, Hu, and Sereni disproved a broader multiplication principle.

Known results

  • Jiang and Zhu proved every triangle-free planar graph is (4m:m)(4m:m)-choosable and exhibited graphs that are not (3m+⌈m/17⌉:m)(3m+\lceil m/17\rceil:m)-choosable.
  • Dvořák, Hu, and Sereni exhibited a 44-choosable graph that is not (8:2)(8:2)-choosable, refuting general multiplication (a:b)⇒(am:bm)(a:b)\Rightarrow(am:bm).
  • Hu and Xu proved every triangle-free planar graph is (15m:4m)(15m:4m)-choosable, answering Jiang–Zhu’s (4m−1:m)(4m-1:m) subquestion positively for m=4m=4.

November 2026 counterexample claim

A November 2026 preprint by Xiaolan Hu and Jiao Li, Counterexamples to Relaxed Multiplication in List Coloring, claims an explicit small counterexample to the stronger implication and therefore a negative answer to the equivalent strong fractional choice-number question. The claim currently rests only on that preprint.

Current status (as of November 2026): The stronger implication is claimed to be false, but its counterexample remains unverified; the earlier partial results are established.

Sources

Solutions 0

No solutions have been posted yet.