Proportional Choice Number

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.