{
  "id": "2008.06333",
  "version": "v1",
  "published": "2020-08-13T03:24:36.000Z",
  "updated": "2020-08-13T03:24:36.000Z",
  "title": "On the Equitable Choosability of the Disjoint Union of Stars",
  "authors": [
    "Hemanshu Kaul",
    "Jeffrey A. Mudrock",
    "Tim Wagstrom"
  ],
  "comment": "20 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Equitable $k$-choosability is a list analogue of equitable $k$-coloring that was introduced by Kostochka, Pelsmajer, and West in 2003. It is known that if vertex disjoint graphs $G_1$ and $G_2$ are equitably $k$-choosable, the disjoint union of $G_1$ and $G_2$ may not be equitably $k$-choosable. Given any $m \\in \\mathbb{N}$ the values of $k$ for which $K_{1,m}$ is equitably $k$-choosable are known. Also, a complete characterization of equitably $2$-choosable graphs is not known. With these facts in mind, we study the equitable choosability of $\\sum_{i=1}^n K_{1,m_i}$, the disjoint union of $n$ stars. We show that determining whether $\\sum_{i=1}^n K_{1,m_i}$ is equitably choosable is NP-complete when the same list of two colors is assigned to every vertex. We completely determine when the disjoint union of two stars (or $n \\geq 2$ identical stars) is equitably 2-choosable, and we present results on the equitable $k$-choosability of the disjoint union of two stars for arbitrary $k$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-08-13T03:24:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "68R10"
    ],
    "keywords": [
      "disjoint union",
      "equitable choosability",
      "vertex disjoint graphs",
      "list analogue",
      "complete characterization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}