The proportional choice number of a finite nonempty simple
graph
is the least positive integer
such that every assignment of a list
of
colors to each graph vertex
admits a proper list coloring in which each color
is used either
or
times. Here
is the number of lists containing
, and
and
are the floor function
and ceiling function, respectively (Kaul et
al. 2019). Thus the use of each color is proportional, up to rounding, to its
availability in the lists.
Mudrock (2026) proved ,
where
is the edge chromatic number. In particular,
every path graph has proportional choice number at
most 4. For positive integers
, the graph disjoint
union of
copies of the complete bipartite graph
has proportional choice number
.
These examples disprove the proposed bound
,
where
is the maximum vertex degree.