Delphi.science

An Upper Bound on the Proportional Choice Number of a Graph

Source: arxiv.org/abs/2611.24740

Kevin Grace, Jeffrey A. Mudrock

arXivarxiv/2611.24740Nov 18, 2026math.COscore 0

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. A recently proposed conjecture states that for any graph $G$ with at least one edge, $χ_{pc}(G) \leq Δ(G) + \text{col}(G) - 1$, where $Δ(G)$ is the maximum degree of $G$ and $\text{col}(G)$ is its coloring number. In this paper, we prove this conjecture…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.24740
curl -X POST /api/v1/records/arxiv/2611.24740/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.24740/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'