betaFeedback

WorksMathematics

Improved Bounds on Proportional Choice Numbers

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. We consider two previously posed questions regarding proportional choice numbers: (1) Is there a constant CC such that χpc(Pn)≤Cχ_{pc}(P_n) \leq C for every n∈Nn \in \mathbb{N}? and (2) Is it the case that for any graph GG, χpc(G)≤Δ(G)+1χ_{pc}(G) \leq Δ(G)+1 where Δ(G)Δ(G) is the maximum degree of GG? In this paper we answer both questions: the first in the affirmative and the second in the negative. Specifically, we prove that χpc(G)≤2χ′(G)χ_{pc}(G) \leq 2^{χ'(G)} for every graph GG where χ′(G)χ'(G) is the chromatic index of GG. Consequently, χpc(Pn)≤4χ_{pc}(P_n) \leq 4 for every n∈Nn \in \mathbb{N}. We also prove that when GG is the disjoint union of (a+b−1)(a+b-1) copies of Ka,bK_{a,b}, χpc(G)=a+bχ_{pc}(G)=a+b. In particular, for each m∈Nm \in \mathbb{N}, there is a graph GG with Δ(G)=mΔ(G)=m and χpc(G)=2Δ(G)χ_{pc}(G)=2Δ(G).

Paper details

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

views · 0

downloads · 0

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

  • Mathematics

ChatGPT, Claude

View statement
Looking for related papers…