{
  "id": "2005.12915",
  "version": "v1",
  "published": "2020-05-26T17:02:59.000Z",
  "updated": "2020-05-26T17:02:59.000Z",
  "title": "Proportional Choosability of Complete Bipartite Graphs",
  "authors": [
    "Jeffrey A. Mudrock",
    "Jade Hewitt",
    "Paul Shin",
    "Collin Smith"
  ],
  "comment": "11 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "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 $\\chi_{pc}(G)$. In the first ever paper on proportional choosability, it was shown that when $2 \\leq n \\leq m$, $ \\max\\{ n + 1, 1 + \\lceil m / 2 \\rceil\\} \\leq \\chi_{pc}(K_{n,m}) \\leq 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\\} \\leq \\chi_{pc}(K_{n,m}) \\leq 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-05-26T17:02:59.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "proportional choosability",
      "complete bipartite graphs",
      "proportional choice number",
      "complete multipartite graphs",
      "list analogue"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}