---

Claim. V. H. Vu, A general upper bound on the list chromatic number of locally sparse graphs, Combin. Probab. Comput. 11 (2002), no. 1, 103--111, doi:10.1017/S0963548301004898; the Crossref record dates the issue January 2002, whose nominal first day is this page's date. The paper's main theorem, as its published abstract states it: if every vertex neighborhood of a graph $G$ of maximum degree $\Delta(G)$ spans at most $\Delta(G)^2/f$ edges, with $f>1$, then the list chromatic number of $G$ is at most $c\Delta(G)/\log f$ for an absolute constant $c>0$, a bound sharp up to the constant. The abstract adds that the paper derives from it several upper bounds on the strong (list) chromatic index under various assumptions, extending earlier results of Faudree, Gyárfás, Schelp and Tuza and of Mahdian. Cames van Batenburg, Kang and Pirot (Indag. Math. 2020, p. 2 of arXiv v1; [[../library/extremal_graph_theory/camesvanbatenburg_2020_strong_cliques_forbidden_cycles/_index|source card]]) describe the extension as Mahdian's $C_4$-free statement with $C_4$ replaced by any bipartite graph $H$: for each fixed bipartite $H$, every $H$-free graph $G$ of maximum degree $\Delta$ has $\mathrm{sq}(G)=O_H(\Delta^2/\log\Delta)$.

The same order follows from the main theorem by the deduction that Bi, Bradshaw, Dhawan and Xu give for $K_{t,t}$-free graphs (arXiv:2603.15207v1, pp. 1--2, through the later Hurley--Pirot form of the theorem): a bipartite $H$ lies in $K_{t,t}$ for $t=|V(H)|$, the graph $L(G)^2$ has maximum degree below $2\Delta^2$, and by the Kővári--Sós--Turán theorem each neighborhood in $L(G)^2$ spans $O(\Delta^{4-1/(t-1)})$ edges, so $f=\Omega(\Delta^{1/(t-1)})$ and the list chromatic number of $L(G)^2$ is $O(\Delta^2/\log\Delta)$. That deduction is this page's, not the paper's text. Once $\Delta$ is large enough that this bound is at most $\frac54\Delta^2$, the bound of Problem 149 holds for these graphs.

Covers. Graphs with no subgraph isomorphic to a fixed bipartite graph $H$ whose maximum degree exceeds a threshold depending on $H$; graphs containing $H$, among them the blown-up five-cycles of large degree, are not covered. For $H=C_4$ it contains the instances of [[problems/extremal_graph_theory/E0149/claims/2000_10_01_mahdian|Mahdian's bound]], with a weaker constant.

Depends on. Nothing in this wiki.

Standing. Claimed. The paper is refereed in Combinatorics, Probability and Computing, but its published abstract does not state the strong-chromatic-index corollary, which is recorded from the account of Cames van Batenburg, Kang and Pirot, so refereed is not listed. The site's thread names the paper (28 October 2025), and the site labels the problem OPEN.