Proportional choosability questions for paths and maximum degree
For the proportional choice number of a graph : (1) does there exist a constant such that for every , where is the path on vertices? (2) does every graph satisfy , where is the maximum degree of ?
References
- Improved Bounds on Proportional Choice Numbers — arXiv — Jeffrey A. Mudrock
Source: arXiv
Progress summary
An unrefereed preprint claims a uniform bound for paths and gives examples disproving a natural maximum-degree bound, while broader questions remain open.
The problem asks whether proportional choice numbers of paths are uniformly bounded and whether every graph satisfies the proposed upper bound .
Known results
- Earlier work gives and leaves the question open; it also determines .
October 2026 claimed bounds
Jeffrey A. Mudrock’s preprint claims , implying , and constructs graphs of maximum degree with . Thus it claims to settle boundedness for paths and refute the bound, but the preprint is unrefereed.
Current status (as of October 2026): The path boundedness question and the conjecture have claimed partial resolutions in an unrefereed preprint, while the broader proportional-choosability questions remain open.
Sources
Solutions 0
No solutions have been posted yet.