The Proportional Choice Number of Complete Bipartite and Complete Multipartite Graphs: Exact Value, Classification, and Asymptotics

Proportional choosability is a list-colouring analogue of equitable colouring introduced in 2019: given a $k$-assignment $L$ of colour lists on a graph $G$, a proportional $L$-colouring must use each colour $c$ exactly $\lfloor \eta_L(c)/k \rfloor$ or $\lceil \eta_L(c)/k \rceil$ times, where $\eta_L(c)$ counts the vertices whose list contains $c$. The smallest such $k$ is the proportional choice number $\chi_{pc}(G)$. For complete bipartite graphs the best known bounds (Mudrock, Hewitt, Shin and Smith, 2021) are $\max\{n+1, \lceil n/2\rceil + \lceil m/2\rceil\} \le \chi_{pc}(K_{n,m}) \le n+m-1-\lfloor m/3 \rfloor$. This record formulates the paper's three open questions about $\chi_{pc}$ on complete bipartite and complete multipartite graphs: whether $\chi_{pc}(K_{n,m}) = \max\{n+1, \lceil n/2\rceil + \lceil m/2\rceil\}$ for all $m \ge n$, whether the analogous two-case formula holds for complete multipartite graphs, and whether $\chi_{pc}(K_{n,m})/m \to 1/2$ for each fixed $n$.

Background

A proper $k$-colouring of a graph $G$ assigns one of $k$ colours to each vertex so that adjacent vertices receive different colours; the chromatic number $\chi(G)$ is the smallest such $k$. An equitable $k$-colouring is a proper $k$-colouring in which the sizes of any two colour classes differ by at most one, so each colour is used neither too little nor too much. A classical theorem of Hajnal and Szemeredi (1970) states that every graph admits an equitable $k$-colouring whenever $k \ge \Delta(G)+1$, where $\Delta(G)$ is the maximum vertex degree.

List colouring is a variant in which each vertex $v$ is given a list $L(v)$ of available colours and must be coloured from its own list; a $k$-assignment is a list assignment with $|L(v)| = k$ for every vertex. A graph is $k$-choosable if it can be properly coloured from every $k$-assignment, and the smallest such $k$ is the list chromatic number $\chi_\ell(G)$. Complete bipartite graphs — $K_{n,m}$, the graph whose vertices split into two disjoint parts of sizes $n$ and $m$ with every cross-edge present and no edges inside a part — are the classical testbed for list colouring: $\chi(K_{n,m}) = 2$ while $\chi_\ell(K_{n,m})$ grows with $n$, so the two invariants are far apart there.

Kostochka, Pelsmajer and West (2003) combined the two themes into equitable choosability: for a $k$-assignment $L$, an equitable $L$-colouring may use each colour at most $\lceil |V(G)|/k \rceil$ times — an upper bound on usage only. Proportional choosability, introduced by Kaul, Mudrock, Pelsmajer and Reiniger (2019), restores the two-sided flavour of equitable colouring. For a $k$-assignment $L$, the multiplicity $\eta_L(c)$ of a colour $c$ in the palette is the number of vertices $v$ with $c \in L(v)$; a proportional $L$-colouring is a proper $L$-colouring in which each colour $c$ is used exactly $\lfloor \eta_L(c)/k \rfloor$ or $\lceil \eta_L(c)/k \rceil$ times — each colour is used proportionally to how available it was. $G$ is proportionally $k$-choosable if a proportional $L$-colouring exists for every $k$-assignment $L$, and the proportional choice number $\chi_{pc}(G)$ is the smallest such $k$ (well-defined because proportional $k$-choosability implies proportional $(k+1)$-choosability, a monotonicity that fails for equitable colouring, e.g. $K_{3,3}$ is equitably 2- but not equitably 3-colourable).

What is known: $\chi_{pc}(G) \le \Delta(G) + \lceil |V(G)|/2 \rceil$ for every graph; the proportionally 2-choosable graphs are exactly the linear forests (disjoint unions of paths) whose largest component has at most 5 vertices, with all other components of at most 2 vertices; $\chi_{pc}(K_{1,m}) = 1 + \lceil m/2 \rceil$ for stars; and $K_{m,m}$ is not proportionally $m$-choosable. The founding paper asks whether the Hajnal–Szemeredi analogue holds: is every graph proportionally $k$-choosable for $k \ge \Delta(G)+1$? This remains open (restated as open in the 2025 survey of Kierstead, Kostochka and Xiang), while the analogous stronger conjecture for equitable choosability provably fails for proportional choosability (a disjoint union of stars is a counterexample).

Mudrock, Hewitt, Shin and Smith (2021) studied $\chi_{pc}$ on complete bipartite graphs, where the invariant behaves strikingly differently from $\chi_\ell$: it grows linearly rather than logarithmically. Their Theorem 6 gives $\max\{n+1, \lceil n/2 \rceil + \lceil m/2 \rceil\} \le \chi_{pc}(K_{n,m}) \le n+m-1-\lfloor m/3 \rfloor$ for $2 \le n \le m$; the lower bound comes from a general result on complete $t$-partite graphs ($\chi_{pc}(K_{n_1,\dots,n_t}) \ge \sum_i \lceil n_i/2 \rceil$), sharpened by one when all parts are even and no part exceeds half the total order (their Proposition 8, whose proof exploits a 1994 characterization of equitable colourability of complete multipartite graphs). They found no counterexample to their lower bound being tight, which is exactly the open problem formulated here.

Problem Statement

The source paper (Mudrock, Hewitt, Shin and Smith, 2021) poses three separate open questions about the proportional choice number of complete bipartite and complete multipartite graphs. These questions are logically nested: (2) implies (1) as its $t=2$ special case, and (1) implies (3), so resolving the classification (2) settles all three; they may equally be resolved independently, and partial progress on any of them is of interest:

(1) Exact value for $K_{n,m}$. For all natural numbers $m \ge n$, is

$$\chi_{pc}(K_{n,m}) = \max\left\{n+1, \left\lceil \frac{n}{2} \right\rceil + \left\lceil \frac{m}{2} \right\rceil\right\}?$$

The inequality $\ge$ is already known (Theorem 6 of the source for $2 \le n \le m$, and the founding paper for the star case $n=1$), and equality holds for $n=1$ (stars); the open content is the matching upper bound, i.e. whether $K_{n,m}$ is proportionally $k$-choosable for every $k$-assignment whenever $k \ge \max\{n+1, \lceil n/2 \rceil + \lceil m/2 \rceil\}$. The best current upper bound is only $n+m-1-\lfloor m/3 \rfloor$ (Theorem 6, for $2 \le n \le m$).

(2) Complete multipartite classification. For $G = K_{n_1,\dots,n_t}$ with $t \ge 2$: if $G$ does not satisfy the balanced-even hypothesis of Proposition 8 (all parts even and the largest part at most half the total order), is $\chi_{pc}(G) = \sum_{i=1}^t \lceil n_i/2 \rceil$ (the Theorem 7 lower bound)? If $G$ does satisfy it, is $\chi_{pc}(G) = 1 + \sum_{i=1}^t n_i/2$ (the Proposition 8 lower bound)?

(3) Asymptotics. For each fixed natural number $n$, is

$$\lim_{m \to \infty} \frac{\chi_{pc}(K_{n,m})}{m} = \frac{1}{2}?$$

Currently $1/2 \le \liminf_{m\to\infty} \chi_{pc}(K_{n,m})/m \le \limsup_{m\to\infty} \chi_{pc}(K_{n,m})/m \le 2/3$ is known. Note that a positive answer to (1) would imply (3) and would confirm the Hajnal–Szemeredi analogue for complete bipartite graphs; moreover, (1) is the $t=2$ special case of the classification (2), so it too is settled by the complete multipartite classification.

References

1. Mudrock, Jeffrey A.; Hewitt, Jade; Shin, Paul; Smith, Collin. Proportional Choosability of Complete Bipartite Graphs. Graphs and Combinatorics 37(1):381-392, 2021. DOI: 10.1007/s00373-020-02255-9. https://doi.org/10.1007/s00373-020-02255-9 (preprint: arXiv:2005.12915, https://arxiv.org/abs/2005.12915)
2. Kaul, Hemanshu; Mudrock, Jeffrey A.; Pelsmajer, Michael J.; Reiniger, Benjamin. Proportional choosability: A new list analogue of equitable coloring. Discrete Mathematics 342(8):2371-2383, 2019. DOI: 10.1016/j.disc.2019.05.011. https://doi.org/10.1016/j.disc.2019.05.011 (preprint: arXiv:1806.06966, https://arxiv.org/abs/1806.06966)
3. Kaul, Hemanshu; Mudrock, Jeffrey A.; Pelsmajer, Michael J.; Reiniger, Benjamin. A Simple Characterization of Proportionally 2-choosable Graphs. Graphs and Combinatorics 36(3):679-687, 2020. DOI: 10.1007/s00373-020-02146-z. https://doi.org/10.1007/s00373-020-02146-z (preprint: arXiv:1806.11265, https://arxiv.org/abs/1806.11265)
4. Mudrock, Jeffrey A.; Piechota, Robert; Shin, Paul; Wagstrom, Tim. Proportional 2-Choosability with a Bounded Palette. Graphs and Combinatorics 38(1), Paper No. 23, 2022. DOI: 10.1007/s00373-021-02448-w. https://doi.org/10.1007/s00373-021-02448-w (preprint: arXiv:1910.03418, https://arxiv.org/abs/1910.03418)
5. Kierstead, H. A.; Kostochka, Alexandr; Xiang, Zimu. Results and Problems on Equitable Coloring of Graphs. Preprint, 2025. arXiv:2504.14711. https://arxiv.org/abs/2504.14711
6. Lih, Ko-Wei. Equitable Coloring of Graphs. In: Handbook of Combinatorial Optimization (living reference work). Springer, online first 2024, print 2025, pp. 1-55. DOI: 10.1007/978-1-4614-6624-6_25-1. https://doi.org/10.1007/978-1-4614-6624-6_25-1
7. Kostochka, A. V.; Pelsmajer, M. J.; West, D. B. A list analogue of equitable coloring. Journal of Graph Theory 44(2):166-177, 2003. DOI: 10.1002/jgt.10137. https://doi.org/10.1002/jgt.10137
8. Hajnal, A.; Szemerédi, E. Proof of a conjecture of P. Erdős. In: Combinatorial Theory and its Applications (Proc. Colloq., Balatonfüred, 1969), Colloquia Mathematica Societatis János Bolyai 4, North-Holland, Amsterdam, 1970, pp. 601-623. zbMATH: Zbl 0217.02601. https://zbmath.org/?q=an:0217.02601