{
  "id": "1507.06513",
  "version": "v1",
  "published": "2015-07-23T14:32:07.000Z",
  "updated": "2015-07-23T14:32:07.000Z",
  "title": "Online Paintability: The Slow-Coloring Game",
  "authors": [
    "Thomas Mahoney",
    "Gregory J. Puleo",
    "Douglas B. West"
  ],
  "comment": "17 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The slow-coloring game is played by Lister and Painter on a graph $G$. On each round, Lister marks a nonempty subset $M$ of the remaining vertices, scoring $|M|$ points. Painter then deletes a subset of $M$ that is independent in $G$. The game ends when all vertices are deleted. Painter's goal is to minimize the total score; Lister seeks to maximize it. The score that each player can guarantee doing no worse than is the cost of $G$, written $\\mathring{s}(G)$. The game is a variant of online list coloring. We prove several results. Always $\\frac{|V(G)|}{2\\alpha(G)}+\\frac{1}{2}\\leq \\frac{\\mathring{s}(G)}{|V(G)|}\\leq \\max\\left\\{\\frac{|V(H)|}{\\alpha(H)}\\colon\\,\\!H \\subset G\\right\\}$, where $\\alpha(G)$ is the independence number. Among $n$-vertex trees, $\\mathring{s}$ is minimized by the star and maximized by the path. Trivially $\\mathring{s}(G)$ is at most the sum-paintability of $G$, with equality only when all components of $G$ are complete. Also $\\mathring{s}(G)$ is at least the chromatic sum (the minimum sum of vertex colors in a proper coloring by positive integers), with equality if $\\alpha(G)\\leq 2$. Finally, we give good bounds on $\\mathring{s}(K_{r,s})$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-07-23T14:32:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C57"
    ],
    "keywords": [
      "slow-coloring game",
      "online paintability",
      "game ends",
      "painters goal",
      "vertex colors"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150706513M"
    }
  }
}