TOPICS
Search

Strong Fractional Choice Number


The strong fractional choice number of a finite simple graph G with at least one graph vertex is the infimum of the real numbers r such that G is (a,b)-choosable for every pair of positive integers a,b with a/b>=r (Li and Zhu 2020, Gu and Xu 2026). Here (a,b)-choosability means that every assignment of lists of a colors to the vertices admits a choice of b colors from each list such that the chosen sets at adjacent vertices are disjoint. The case b=1 is ordinary list coloring. The strong fractional choice number is denoted ch_f^s(G). Its definition requires the stated coloring property for every denominator b, rather than for just a selected ratio a/b.

Gu and Xu (2026, Theorem 1.4) proved that, for all integers t>=0 and b>=7t+2, there is a planar graph with choice number 3 that is not (3b+t,b)-choosable. In particular, their construction gives a planar graph on 121 vertices that is 3-choosable but not (6,2)-choosable. Consequently,

 sup{ch_f^s(G):G is planar and ch(G)=3}>=(22)/7,

where sup denotes the supremum. For every choice of integers k>=4, t>=0, and b>=3t+2, Gu and Xu (2026, Theorem 1.6) construct a graph with choice number k that is not (kb+t,b)-choosable. Thus

 sup{ch_f^s(G):ch(G)=k}>=k+1/3.

See also

Choice Number, List Coloring

Explore with Wolfram|Alpha

References

Gu, Y. and Xu, R. "The Strong Fractional Choice Number Can Exceed the Choice Number." 2 Nov 2026. https://arxiv.org/abs/2611.03236v1.Li, X. and Zhu, X. "The Strong Fractional Choice Number of Series-Parallel Graphs." Disc. Math. 343, 111796, 2020. https://doi.org/10.1016/j.disc.2019.111796.

Cite this as:

Weisstein, Eric W. "Strong Fractional Choice Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/StrongFractionalChoiceNumber.html

Subject classifications