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 G, denoted by χpc(G), is the smallest positive integer k such that G is proportionally k-choosable. We consider two previously posed questions regarding proportional choice numbers: (1) Is there a constant C such that χpc(Pn) ≤ C for every n ∈ ℕ? and (2) Is it the case that for any graph G, χpc(G) ≤ Δ(G)+1 where Δ(G) is the maximum degree of G? 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) for every graph G where χ'(G) is the chromatic index of G. Consequently, χpc(Pn) ≤ 4 for every n ∈ ℕ. We also prove that when G is the disjoint union of (a+b−1) copies of Ka,b, χpc(G)=a+b. In particular, for each m ∈ ℕ, there is a graph G with Δ(G)=m and χpc(G)=2Δ(G).
Related
- Improved bounds on the b-chromatic number using the independence and chromatic numbers
- Contraction-Based Model Predictive Control using Bilinear Koopman Realizations with Proportional Error Bounds
- An Improved Upper Bound for Multicolour Ramsey Numbers
- Improved bounds for the two-point logarithmic Chowla conjecture
- Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs
BibTeX
@misc{mudrock2026improved,
title = {{Improved Bounds on Proportional Choice Numbers}},
author = {Jeffrey A. Mudrock},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33914},
eprint = {2610.33914},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33914},
}
RIS
TY - UNPB
TI - Improved Bounds on Proportional Choice Numbers
AU - Jeffrey A. Mudrock
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33914
UR - https://arxiv.org/abs/2610.33914
AB - 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 G, denoted by χ_pc(G), is the smallest positive integer k such that G is proportionally k-choosable. We consider two previously posed questions regarding proportional choice numbers: (1) Is there a constant C such that χ_pc(P_n) ≤ C for every n ∈ ℕ? and (2) Is it the case that for any graph G, χ_pc(G) ≤ Δ(G)+1 where Δ(G) is the maximum degree of G? 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) for every graph G where χ'(G) is the chromatic index of G. Consequently, χ_pc(P_n) ≤ 4 for every n ∈ ℕ. We also prove that when G is the disjoint union of (a+b−1) copies of K_a,b, χ_pc(G)=a+b. In particular, for each m ∈ ℕ, there is a graph G with Δ(G)=m and χ_pc(G)=2Δ(G).
ER -