WorksMathematics
An Upper Bound on the Proportional Choice Number of a Graph
Abstract
Proportional choosability is a list analogue of equitable coloring introduced in 2019 that imposes both upper and lower bounds on color class sizes based on the availability of each color. The proportional choice number of a graph , denoted by , is the smallest positive integer such that is proportionally -choosable. A recently proposed conjecture states that for any graph with at least one edge, , where is the maximum degree of and is its coloring number. In this paper, we prove this conjecture using a generalization of Edmonds' matroid intersection theorem due to Aharoni and Berger, in which one of the matroids is replaced with an abstract simplicial complex. As a consequence, we can completely determine the proportional choice number of every path: , for , and for . This resolves a question about paths that has remained open since the introduction of proportional choosability.