{
  "id": "1808.02018",
  "version": "v1",
  "published": "2018-08-04T18:21:52.000Z",
  "updated": "2018-08-04T18:21:52.000Z",
  "title": "A Note on the Equitable Choosability of Complete Bipartite Graphs",
  "authors": [
    "Jeffrey A. Mudrock",
    "Madelynn Chase",
    "Isaac Kadera",
    "Ezekiel Thronburgh"
  ],
  "comment": "6 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In 2003 Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. A $k$-assignment, $L$, for a graph $G$ assigns a list, $L(v)$, of $k$ available colors to each $v \\in V(G)$, and an equitable $L$-coloring of $G$ is a proper coloring, $f$, of $G$ such that $f(v) \\in L(v)$ for each $v \\in V(G)$ and each color class of $f$ has size at most $\\lceil |V(G)|/k \\rceil$. Graph $G$ is said to be equitably $k$-choosable if an equitable $L$-coloring of $G$ exists whenever $L$ is a $k$-assignment for $G$. In this note we study the equitable choosability of complete bipartite graphs. A result of Kostochka, Pelsmajer, and West implies that $K_{n,m}$ is equitably $k$-choosable if $k \\geq \\max \\{n,m\\}$. We prove $K_{n,m}$ is equitably $k$-choosable if $m \\leq \\left\\lceil (m+n)/k \\right \\rceil(k-n)$ which gives $K_{n,m}$ is equitably $k$-choosable for certain $k$ satisfying $k < \\max \\{n,m\\}$. We also give a complete characterization of the equitable choosability of stars (i.e. graphs of the form $K_{1,m}$).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-08-04T18:21:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "complete bipartite graphs",
      "equitable choosability",
      "color class",
      "assignment",
      "list analogue"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}