betaFeedback

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 GG, denoted by χpc(G)χ_{pc}(G), is the smallest positive integer kk such that GG is proportionally kk-choosable. A recently proposed conjecture states that for any graph GG with at least one edge, χpc(G)≤Δ(G)+col(G)−1χ_{pc}(G) \leq Δ(G) + \text{col}(G) - 1, where Δ(G)Δ(G) is the maximum degree of GG and col(G)\text{col}(G) 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: χpc(P1)=1χ_{pc}(P_1)=1, χpc(Pn)=2χ_{pc}(P_n)=2 for 2≤n≤52 \leq n \leq 5, and χpc(Pn)=3χ_{pc}(P_n)=3 for n≥6n \geq 6. This resolves a question about paths that has remained open since the introduction of proportional choosability.

Paper details

vlnc:W_uudybcx4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…