2020/05/26 by Mudrock, Jeffrey A., Hewitt, Jade, Shin, Paul +1
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2005.12915
Proportional choosability is a list analogue of equitable coloring that was introduced in 2019. The smallest k for which a graph G is proportionally k-choosable is the proportional choice number of G, and it is denoted χpc(G). In the first ever paper on proportional choosability, it was shown that when 2 ≤ n ≤ m, max\ n + 1, 1 + \lceil m / 2 \rceil\ ≤ χpc(Kn,m) ≤ n + m - 1. In this note we improve on this result by showing that max\ n + 1, \lceil n / 2 \rceil + \lceil m / 2 \rceil\ ≤ χpc(Kn,m) ≤ n + m -1- \lfloor m/3 \rfloor. In the process, we prove some new lower bounds on the proportional choice number of complete multipartite graphs. We also present several interesting open questions.