← All problems

Proportional choosability questions for paths and maximum degree

For the proportional choice number χpc(G)\chi_{pc}(G) of a graph GG: (1) does there exist a constant CC such that χpc(Pn)≤C\chi_{pc}(P_n)\le C for every n∈Nn\in\mathbb{N}, where PnP_n is the path on nn vertices? (2) does every graph GG satisfy χpc(G)≤Δ(G)+1\chi_{pc}(G)\le\Delta(G)+1, where Δ(G)\Delta(G) is the maximum degree of GG?

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 χpc(G)≤Δ(G)+1\chi_{pc}(G) \le \Delta(G)+1.

Known results

  • Earlier work gives χpc(G)≤Δ(G)+⌈∣V(G)∣/2⌉\chi_{pc}(G) \le \Delta(G)+\lceil |V(G)|/2\rceil and leaves the Δ(G)+1\Delta(G)+1 question open; it also determines χpc(K1,m)=1+⌈m/2⌉\chi_{pc}(K_{1,m})=1+\lceil m/2\rceil.

October 2026 claimed bounds

Jeffrey A. Mudrock’s preprint claims χpc(G)≤2χ′(G)\chi_{pc}(G) \le 2^{\chi'(G)}, implying χpc(Pn)≤4\chi_{pc}(P_n) \le 4, and constructs graphs of maximum degree mm with χpc=2m\chi_{pc}=2m. Thus it claims to settle boundedness for paths and refute the Δ(G)+1\Delta(G)+1 bound, but the preprint is unrefereed.

Current status (as of October 2026): The path boundedness question and the Δ(G)+1\Delta(G)+1 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.